= Solution
With $i$ processed <points>, a triangulated three-dimensional <convex hull> has $O(i)$ faces and edges. For a sphere-like triangular boundary, the <Euler characteristic> and $3F=2E$ give $F=2V-4$ and $E=3V-6$, with $V\le i$. The complete face scan, horizon construction and adjacency update in the implementation of part (e) therefore cost $O(i)$ per insertion. Consequently,
$$
\boxed{T(n)=O\!\left(\sum_{i=4}^{n-1}i\right)=O(n^2),\qquad\text{working storage }O(n).}
$$
The quadratic worst case really occurs for this implementation. Choose all input <points> in strictly <convex> position, for example distinct <points> $(t,t^2,t^3)$ on the three-dimensional <moment curve>. Each processed <point> remains a hull <vertex of a polyhedron>, so the hull has $2i-4$ triangular faces after $i$ insertions. Scanning every face at every next insertion takes $\Theta(n^2)$ sign tests. This argument does not require every insertion to delete most faces: the repeated global scans already force the bound. More elaborate <convex hull> algorithms with different search machinery are not the implementation being analysed here.
Back to article page
