**Next:** Problem 4: Union of Fat Objects in 3D

**Previous:** Problem 2: Voronoi Diagram of Moving Points

- 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^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 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
- 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):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.