P. Angelier and M. Pocchiola.
A sum of squares theorem for visibility complexes and applications.
In B. Aronov, S. Basu, J. Pach, and M. Sharir, editors,
Discrete and Computational Geometry -
Algorithms and Combinatorics¸ volume 25, pages 79-139. Springer-Verlag,
We present a new method to implement in constant amortized time
the flip operation of the so-called Greedy Flip Algorithm,
algorithm to compute the
visibility complex of a collection of pairwise disjoint bounded
of constant complexity (disks).
The method uses simple data structures and only
the left-turn predicate for disks;
it relies, among other things, on a sum of squares like theorem for
visibility complexes stated and proved in this paper.
(The sum of squares
theorem for a simple
arrangement of lines states that the average value of the square
of the number of vertices of a face of the arrangement is bounded by a
A 'sum of squares' theorem for visibility complexes (extended abstract).
In Proc. 17th Annu. ACM Sympos. Comput. Geom.,
pages 302-311, June 2001.
Technical report version 2001
European Workshop on Comput. Geom. 2000 version