Home » Projects » Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes

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

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
Möbuis diagram	points \(p_i\) with scalars \(\lambda_i\), \(\mu_i\)		circles and lines
Anisotropic diagram	points \(p_i\) with positive definite matrices \(M_i\), and scalars \(\pi_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 & Links

This work is related to the Arrangements of Geodesic Arcs on the Sphere. Visit the project page for more details, including an online movie!
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 IX, Volume 6290 of LNCS, pages 1–27, Springer, 2010, [link][bibtex]
In Proceedings of the 6^th 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 25^th European Workshop on Computational Geometry (EuroCG), 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 [pdf][bibtex]
arXiv:0906.2760v1, 2009 [link][bibtex][exam presentation]

Contacts

Ophir Setter

Dan Halperin

@article{s-ctdvdd-09,
  author       = {Ophir Setter},
  title        = {Constructing Two-Dimensional {V}oronoi Diagrams via Divide-and-Conquer of Envelopes in Space},
  journal      = {CoRR},
  volume       = {abs/0906.2760},
  year         = {2009},
  url          = {http://arxiv.org/abs/0906.2760},
  eprinttype   = {arXiv},
  eprint       = {0906.2760},
  timestamp    = {Mon, 13 Aug 2018 16:47:01 +0200},
  biburl       = {https://dblp.org/rec/journals/corr/abs-0906-2760.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@mastersthesis{s-ctdvdd-09,
  author       = {Ophir Setter},
  title        = {Constructing Two-Dimensional {V}oronoi Diagrams via Divide-and-Conquer of Envelopes in Space},
  school       = {The Blavatnik School of Computer Science, Tel-Aviv University},
  year         = {2009},
  address      = {Tel-Aviv, Israel},
  month        = {May},
  type         = {M.{Sc}. Thesis}
}

@inproceedings{sh-ecmwad-09,
  title        = {Exact Construction of Minimum-Width Annulus of Disks in the Plane},
  author       = {Ophir Setter and Dan Halperin},
  booktitle    = {Abstracts of 25th European Workshop on Computational Geometry ({EuroCG})},
  pages        = {317--320},
  month        = {March},
  year         = {2009},
  site         = {Brussels, Belgium}
}

@inproceedings{ssh-ctdvd-09,
  author    = {Ophir Setter and Micha Sharir and Dan Halperin},
  title     = {Constructing two-dimensional {V}oronoi diagrams via divide-and-conquer of envelopes in space},
  booktitle = {Proceedings of the 6th International Symposium on Voronoi Diagrams ({ISVD})},
  year      = {2009},
  pages     = {43--52},
  doi       = {10.1109/ISVD.2009.20}
}

@incollection{ssh-ctdvd-10,
  author    = {Ophir Setter and Micha Sharir and Dan Halperin},
  title     = {Constructing two-dimensional {V}oronoi diagrams via divide-and-conquer of envelopes in space},
  journal   = {Transactions on Computational Sciences IX: Special Issue on V{}oronoi Diagrams in Science and Engineering},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {6290},
  year      = {2010},
  pages     = {1--27},
  doi       = {10.1007/978-3-642-16007-3_1}
}

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]