Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes
Computing the Voronoi diagram of a set of points using the lower envelope of planes |
Abstract
We present a general framework for implementing exact two-dimensional Voronoi diagrams of different classes of sites under various distance functions. The computation of the diagrams employs CGAL (the Computational Geometry Algorithm Library) for constructing envelopes of surfaces in 3-space, which implements a divide-and-conquer algorithm. A straightforward application of the divide-and-conquer approach for Voronoi diagrams yields algorithms, which are highly inefficient in the worst case. We show that through randomization, the expected running time is near-optimal (in the worst case). We also show how the framework can be used, together with existing tools from CGAL, to compute a minimum-width annulus of a set of disks in the plane. This requires the construction of two Voronoi diagrams of different types (one type of which appears not to have been investigated before) and of the overlay of the two diagrams. For all the diagrams discussed in the paper the implementation is exact and can handle degenerate inputs.
A variety of Voronoi diagrams can be computed using our robust framework. Some of these are depicted below. Sites are drawn in red and Voronoi edges are drawn in blue.
Nearest-Neighbor Voronoi Diagrams in the Plane
(a) | (b) | (c) | (d) |
(a) A standard Voronoi diagram (point sites with Euclidean metric). (b) An additively-weighted Voronoi(Apollonius) diagram with disk centers as sites and disk radii as weights. (c) A Mobuis diagram with disk centers as sites. The distance from every point on the boundary of a disk to its corresponding site is zero. (d) A Voronoi diagram of segments. *The sites in (b), (c), and (d) are displayed as dashed curves. |
Farthest-Neighbor Voronoi Diagrams in the Plane
(a) | (b) | (c) | (d) |
(a) A farthest point Voronoi diagram. (b) A farthest additively-weighted Voronoi diagram. (c) A farthest Mobius diagram. (d) A farthest Voronoi diagram of segments. |
Degenerate Voronoi Diagrams in the Plane
(a) | (b) | (c) |
(a) A degenerate standard Voronoi diagram. (b) A degenerate additively-weighted Voronoi (Apollonius) diagram. (c) A degenerate Voronoi diagram of segments |
Voronoi Diagrams on the Sphere
(a) | (b) | (c) | (d) |
(a) The Voronoi diagram of 32 random points. (b) A highly degenerate case of Voronoi diagram of 30 point sites on the sphere. (c) The power diagram of 10 random circles. (d) A degenerate power diagram of 14 site on the sphere. |
Supported Types of Voronoi Diagrams
The table below summarizes the types of diagrams that are currently supported by our implementation and their bisector classes.
Name | Sites | Distance function | Class of bisectors |
---|---|---|---|
Standard Voronoi diagram |
points p_{i} | lines | |
Power diagram | disks (with center c_{i} and radius r_{i} ) | lines | |
2-point triangle- area Voronoi diagram |
pairs of points {p_{i}, q_{i}} | pairs of lines | |
Apollonius diagram |
points p_{i} and weights w_{i} | hyperbolic arcs | |
Möbuis diagram | points p_{i} with scalars λ_{i}, μ_{i} | |
circles and lines |
Anisotropic diagram | points p_{i} with positive definite matrices M_{i}, and scalars π_{i} | conic arc | |
Voronoi diagrams of linear objects |
points, segments, rays, and lines | Eucledian distance | piecewise algebraic curves composed of line segments and parabolic arcs |
Spherical Voronoi diagram | points on a sphere | geodesic distance | arcs of great circles (geodesic arcs) |
Power diagram on a sphere | circles on a sphere | "spherical” power distance | arcs of great circles (geodesic arcs) |
FAQ
Frequently Asked Questions | |
---|---|
Q |
How can I download and use the package? |
A | The code is still experimental and will be available in the future. |
Q |
Can the framework be use for producing power diagrams of weighted points in the plane? |
A | Indeed, our framework allows the production of various types of Voronoi diagrams represented as CGAL arrangements. The main advantage of the framework is the easy (in terms of development) production of Voronoi diagrams rather than efficiency and speed of computation. The reason is that the framework relies on bisector construction and exact computation. If you are looking for a fast and easy production of power diagrams, I refer you to the triangulation package of CGAL. The code can compute regular triangulations (which are the dual to power diagrams) that can be then adapted to Voronoi diagrams using the Voronoi diagram adaptor. |
Q |
Can the framework be use for computing weighted medial axis? |
A | The framework allows the computation of Voronoi diagrams of segments by constructing the lower envelope of their distance functions. If the bisectors of the requested diagrams are quadratic curves in the plane then it is possible to adapt the segments diagram code to support weighted distances. |
Related Project
This work is related to the Arrangements of Geodesic Arcs on the Sphere. Visit the project page for more details, including an online movie!
Links
- Ophir Setter, Micha Sharir, and Dan Halperin.
Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space,
In Transactions on Computational Sciences, 9: 1-27, Springer, 2010, [link] [bibtex]
In Proceedings of the 6th International Symposium on Voronoi Diagrams (ISVD), pages 43-52, 2009 [link] [bibtex]
- Ophir Setter and Dan Halperin
Exact Construction of Minimum-Width Annulus of Disks in the Plane,
In Abstracts of the 25th European Workshop on Computational Geometry (EWCG), pages 317-320, Brussels, Belgium, March 2009 [pdf] [bibtex] [presentation] - Ophir Setter
Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space,
M.Sc. thesis, The Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel, May 2009.
e-print: The ACM Computing Research Repository, abs/0906.2760, June 2009 [thesis] [bibtex] [exam presentation]
Contact
Ophir Setter | ||
Dan Halperin |