Personal tools
You are here: Home Projects Internal Projects Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes
« June 2017 »
June
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
252627282930
Log in


Forgot your password?
 

Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes

Computing Voronoi diagram of points using lower envelope
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

 

Points Nearest Apollonius nearest Mobius Nearest Segments Nearest
(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

 

Points Farthest Apollonius Farthest Mobius Farthest Segments Farthest
(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

 

Points Degenerate Apollonius Degenerate Segments Degenerate
(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

 

Voronoi Degenerate Voronoi Power Diagram Degenerate Power Diagram
(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 pi Points distance function
lines
Power diagram disks (with center ci and radius ri ) Power distance function
lines
2-point triangle-
area Voronoi
diagram
pairs of points {pi, qi} Triangle area
pairs of lines
Apollonius
diagram
points pi and weights wi Apollonius distance function
hyperbolic arcs
Möbuis diagram points pi with scalars λi, μi  Mobius distance function
circles and lines
Anisotropic diagram points pi with positive definite matrices Mi, and scalars πi  Anisotropic distance function 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 faded home ophirset@post.tau.ac.il
Dan Halperin http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Document Actions