The Voronoi diagram of three lines

1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We give a complete description of the Voronoi diagram, in $\R^3$, of three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. In particular, we show that the topology of the Voronoi diagram is invariant for three such lines. The trisector consists of four unbounded branches of either a non-singular quartic or of a non-singular cubic and a 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. We introduce a proof technique, which relies heavily upon modern tools of computer algebra, and 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.
Type de document :
Article dans une revue

Littérature citée [5 références]

https://hal.inria.fr/inria-00431518
Contributeur : Sylvain Lazard <>
Soumis le : jeudi 12 novembre 2009 - 14:44:51
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : mardi 16 octobre 2012 - 13:46:30

Fichier

Voronoi3lines_revised.pdf
Fichiers produits par l'(les) auteur(s)

Citation

Hazel Everett, Daniel Lazard, Sylvain Lazard, Mohab Safey El Din. The Voronoi diagram of three lines. Journal of Discrete and Computational Geometry, Springer, 2009, 42 (1), pp.94-130. 〈http://www.springerlink.com/content/f5601q6324664k2p/?p=6d7bb74bf9df40b0b7756b3a5153809f&pi=5〉. 〈10.1007/s00454-009-9173-3〉. 〈inria-00431518〉

Métriques

Consultations de la notice

407

Téléchargements de fichiers