Search
Close this search box.

Exact Voronoi Diagram of Arbitrary Lines in Space

This is a joint project with Geometrica.

Abstract

We introduce a new, efficient, and complete algorithm, and its exact implementation, to compute the Voronoi diagram of lines in three-dimensions. This is a major milestone towards the robust construction of the Voronoi diagram of polyhedra. Following the exact geometric computation paradigm, it is guaranteed that we always computes the mathematically correct result. The algorithm is complete in the sense that it can handle all configurations, in particular all degenerate ones. The algorithm requires \(O(n^{3+\epsilon})\) time and space, where n is the number of lines. The Voronoi diagram is represented by a data structure that permits answering point location queries in  \(O(\log^2 n)\) expected time. The implementation employs the CGAL packages for constructing arrangements and lower envelopes on parametric surfaces together with advanced algebraic tools.

Bisectors

The bisector of two lines in space

(a)

(b)

(c)

(a) Two generic lines—Hyperbolic paraboloid
(b) Parallel lines—a plane
(c) Two intersecting lines—pair of orthogonal planes

More Diagrams

(a)

(b)

(c)

(a) Four lines intersecting at a single point
(b) Four lines—2 intersect and 2 others are parallel to each of them
(c) Five parallel lines

Open Question and Further Work

  •  A tight bound on the combinatorial complexity of the Voronoi diagram of  \(n\) lines or line segments in \(\mathbb{R}^3\) is unknown; it is conjectured that the complexity is near-quadratic; the known lower bound is \(\Omega(n^2)\), but the best known upper bound is \(O(n^{3+\epsilon})\). In the case of lines with a fixed number \(c\) of orientations the upper bound was improved to \(O(c^4 n^{2+\epsilon})\). Thus, the open question is to close this gap.
  • The exact computation is currently based on pure algebraic methods, which slows down the algorithm. Thus, it is necessary to introduce filters that avoid the use of exact arithmetic. Moreover, it would be useful to decrease the complexity of algebraic methods.
  • So far it is only possible to compute the Voronoi diagram of lines. The next steps are to allow also line segments, points, triangles, and finally polyhedra.

Links

  • Michael Hemmer, Ophir Setter, and Dan Halperin
    Constructing the Exact Voronoi Diagram of Arbitrary Lines in Space with Fast Point-Location
    Preliminary version [pdf]
    Report [link]
    In Proceedings of the 18th Annual European Symposium on Algorithms (ESA) 2010, Volume 6346 of LNCS, pp 398–409 [link][bibtex]
  • The CGAL package for constructing 3D Voronoi diagram of lines including the point location structure [tgz]
  • The internal CGAL on which the package is based on [tgz]
  • CGAL homepage: www.cgal.org

Contacts

Michael Hemmer
Ophir Setter
Dan Halperin
@inproceedings{hsh-cevda-10,
  author = {Michael Hemmer and Ophir Setter and Dan Halperin},
  editor = {Mark de Berg and Ulrich Meyer},
  series = {Lecture Notes in Computer Science ({LNTCS})},
  volume = {6346},
  title = {Constructing the Exact Voronoi Diagram of Arbitrary Lines in Three-Dimensional Space},
  booktitle = {Proceedings of the 18th Annual European Symposium on Algorithms (ESA)},
  year = {2010},
  publisher = {Springer},
  pages = {398--409},
  doi = {10.1007/978-3-642-15775-2_34}
}

Yair Oz - Webcreator

Contact

Skip to content