We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the structure of the 1-skeleton of a polyhedron defined as the intersection of a set of \(n\) halfspaces in \(\mathbb{R}^3\) as a new halfspace is added. To that effect, we define an abstract update operation for planar graphs that can be used to model the addition of new halfspaces to the polyhedron. Moreover, this operation can also be used to model the addition of a new site in several variants of Voronoi diagrams.

Using this abstraction, we show that the amortized number of edge insertions and removals needed to maintain the combinatorial structure of the polyhedron as a new halfspace (or a new site to the Voronoi diagram) is added is \(O(\sqrt{n})\) amortized. A matching \(\Omega(\sqrt{n})\) combinatorial lower bound is shown for this abstract operation. These results provide the first evidence of the existence of an algorithm to incrementally construct the intersection of $n$ halfspaces in sub-quadratic time. Indeed, we present an algorithm running in $O(n^{3/2} \text{polylog } n)$ time for the special case where the 1-skeleton of the polyhedron is always a tree.

This is joint work with Sarah Allen, John Iacono and Stefan Langerman.