Exact and Effcient Construction of General Two-Dimensional Voronoi Diagrams via Divide and Conquer of Envelopes in Space

different site classes under various distance functions. The computation of the diagrams employs
the CGAL software for constructing envelopes of surfaces in 3-space, which implements a
divide-and-conquer algorithm. A straightforward usage of the divide-and-conquer approach for
Voronoi diagrams yields highly ineffcient algorithms. We show that through randomization,
the expected running time is near-optimal (in a worst-case sense). We describe the interface
between the construction of the diagrams and the underlying construction of the envelopes,
together with methods we have applied to speed up the computation. We then present results,
obtained with our implementation, of a variety of diagrams, including power diagrams, Apollonius
diagrams, diagrams of line segments, Voronoi diagram on a sphere, and more. In all cases
the implementation is exact and can handle degenerate input.