# The Voronoi Diagram of Three Lines

Tuesday, May 29, 2007 - 3:10pm - 3:40pm

EE/CS 3-180

Sylvain Lazard (Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine)

We give a complete description of the Voronoi diagram of three lines in

three-dimensional real space. 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.

three-dimensional real space. 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.