Next: Problem 4: Union of
Up: The Open Problems Project
Previous: Problem 2: Voronoi Diagram
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
Ω(n^{2}) 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 nearquadratic complexity [AS00b].
 Related Open Problems
 This problem is closely related to Problem 2,
because points moving in the plane with constant velocity yield
straightline trajectories in spacetime.
 Appearances
 [MO01]
 Categories
 Voronoi diagrams
 Entry Revision History
 J. O'Rourke, 2 Aug. 2001; 13 Dec. 2001.
 AS00b

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

JeanDaniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec.
Voronoi diagrams in higher dimensions under certain polyhedral
distance functions.
Discrete Comput. Geom., 19(4):473484, 1998.
 MO01

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

Micha Sharir.
Almost tight upper bounds for lower envelopes in higher dimensions.
Discrete Comput. Geom., 12:327345, 1994.
The Open Problems Project  September 19, 2017