HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Constructing the Exact Voronoi Diagram of Arbitrary Lines in Space

Michael Hemmer 1, * Ophir Setter 2 Dan Halperin 2
* Corresponding author
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We introduce a new, efficient, and complete algorithm, and its exact implementation, to compute the Voronoi diagram of lines in space. This is a major milestone towards the robust construction of the Voronoi diagram of polyhedra. As we follow the exact geometric-computation paradigm, it is guaranteed that we always compute 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+\varepsilon})$ 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. Supplementary material and in particular the prototypical code of our implementation can be found in the website: http://acg.cs.tau.ac.il/projects/internal-projects/3d-lines-vor/project-page.
Document type :
Complete list of metadata

Contributor : Michael Hemmer Connect in order to contact the contributor
Submitted on : Monday, May 3, 2010 - 2:02:55 PM
Last modification on : Thursday, January 20, 2022 - 5:29:07 PM
Long-term archiving on: : Thursday, September 16, 2010 - 1:21:01 PM


Files produced by the author(s)


  • HAL Id : inria-00480045, version 1



Michael Hemmer, Ophir Setter, Dan Halperin. Constructing the Exact Voronoi Diagram of Arbitrary Lines in Space. [Research Report] RR-7273, INRIA. 2010, pp.19. ⟨inria-00480045⟩



Record views


Files downloads