Voronoi diagram of lines in three dimensions
Consider $n$ lines, or $n$ line segments, in $\mathbb{R}^3$ and their Voronoi diagram.
For the Euclidean distance the complexity lies between a lower bound of $\Omega(n^2)$ and an essentially cubic upper bound that follows from Sharir's bounds on lower envelopes. Under polyhedral distance functions, Boissonnat, Sharir, Tagansky and Yvinec showed the diagram has quadratic complexity. Agarwal and Sharir proved that a union of congruent cylinders around the lines, which is a level set of the distance to the lines, has near-quadratic complexity. Since points moving at constant velocity in the plane trace lines in space-time, the question is close to that of the Voronoi diagram of linearly moving points.
Problem. For $n$ lines, or $n$ line segments, in three dimensions, what is the combinatorial complexity of their Voronoi diagram?
Source: Origin uncertain; Problem 3 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- lower envelopes, The Open Problems Project, Voronoi diagram of lines
References
@article{sharir1994,
author = {Sharir, Micha},
title = {Almost tight upper bounds for lower envelopes in higher dimensions},
journal = {Discrete Comput. Geom.},
volume = {12},
year = {1994},
pages = {327--345},
}
@article{boissonnat1998,
author = {Boissonnat, Jean-Daniel and Sharir, Micha and Tagansky, Boaz and Yvinec, Mariette},
title = {Voronoi diagrams in higher dimensions under certain polyhedral distance functions},
journal = {Discrete Comput. Geom.},
volume = {19},
number = {4},
year = {1998},
pages = {473--484},
}
@article{agarwal2000,
author = {Agarwal, Pankaj K. and Sharir, Micha},
title = {Pipes, cigars, and kreplach: The union of {M}inkowski sums in three dimensions},
journal = {Discrete Comput. Geom.},
volume = {24},
number = {4},
year = {2000},
pages = {645--685},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01068, "Voronoi diagram of lines in three dimensions", clopen.solutions.