A sum of squares theorem for visibility
Pierre Angelier, Michel Pocchiola · 2001
We present a new and simpler method to implement in constant amortized time the flip operation of the so-called “Greedy Flip Algorithm”, an optimal algorithm to compute the visibility complex of a collection of pairwise disjoint bounded convex sets of constant complexity. The method relies on a “sum of squares” like theorem for visibility complexes stated and proved in this paper. (The sum of squares theorem for an arrangement of lines states that the average value of the square of the number of vertices of a face of the arrangement is a $O(1)$.)