Problem 3: Voronoi Diagram of Lines in 3D

Statement

What is the combinatorial complexity of the Voronoi diagram of a set of lines (or line segments) in three dimensions?

Origin

Uncertain, pending investigation.

Status/Conjectures

Open. Conjectured to be nearly quadradic.

Partial and Related Results

There is a gap between a lower bound of $\Omega$(n²) and an upper bound that is essentially cubic [Sha94] for the Euclidean case (and yet is quadratic for polyhedral metrics [BSTY98]). A recent advance shows that the ``level sets'' of the Voronoi diagram of lines, given by the union of a set of cylinders, indeed has near-quadratic complexity [AS00b].

Related Open Problems

This problem is closely related to Problem 2, because points moving in the plane with constant velocity yield straight-line trajectories in space-time.

Appearances

[MO01]

Categories

Voronoi diagrams

Entry Revision History

J. O'Rourke, 2 Aug. 2001; 13 Dec. 2001.

Bibliography

AS00b

Pankaj K. Agarwal and Micha Sharir.
Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions.
Discrete Comput. Geom., 24(4):645-685, 2000.

BSTY98

Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec.
Voronoi diagrams in higher dimensions under certain polyhedral distance functions.
Discrete Comput. Geom., 19(4):473-484, 1998.

MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573-582, 2001.
Also in SIGACT News 32(3):63-72 (2001), Issue 120.

Sha94

Micha Sharir.
Almost tight upper bounds for lower envelopes in higher dimensions.
Discrete Comput. Geom., 12:327-345, 1994.