Past exam of the computer science course of the University of Oxford / 2015 / Geometric modelling / 3 / f

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,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.