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
Conference papers

The Voronoi Diagram of Three Lines

Hazel Everett 1 Daniel Lazard 2 Sylvain Lazard 1 Mohab Safey El Din 2
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We give a complete description of the Voronoi diagram of three lines in $\R^3$. In particular, we show that the topology of the Voronoi diagram is invariant for three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. The trisector consists of four unbounded branches of either a non-singular quartic or of a cubic and line that do not intersect in real space. Each cell of dimension two consists of two connected components on a hyperbolic paraboloid that are bounded, respectively, by three and one of the branches of the trisector. The proof technique, which relies heavily upon modern tools of computer algebra, is of interest in its own right. This characterization yields some fundamental properties of the Voronoi diagram of three lines. In particular, we present linear semi-algebraic tests for separating the two connected components of each two-dimensional Voronoi cell and for separating the four connected components of the trisector. This enables us to answer queries of the form, given a point, determine in which connected component of which cell it lies. We also show that the arcs of the trisector are monotonic in some direction. These properties imply that points on the trisector of three lines can be sorted along each branch using only linear semi-algebraic tests.
Document type :
Conference papers
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download

Contributor : Sylvain Lazard Connect in order to contact the contributor
Submitted on : Wednesday, November 7, 2007 - 7:41:33 PM
Last modification on : Friday, January 21, 2022 - 4:13:15 AM
Long-term archiving on: : Monday, April 12, 2010 - 1:38:03 AM


Files produced by the author(s)



Hazel Everett, Daniel Lazard, Sylvain Lazard, Mohab Safey El Din. The Voronoi Diagram of Three Lines. 23rd Annual Symposium on Computational Geometry (SoCG'07), Hee-Kap Ahn, Otfried Cheong, and Kyung-Yong Chwa, Jun 2007, Gyeongju, South Korea. pp.255-264, ⟨10.1145/1247069.1247116⟩. ⟨inria-00186085⟩



Record views


Files downloads