Voronoi Diagram of Lines in 3D

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

Abstract

For a set of lines or line segments in three-dimensional space, the open question is to determine the combinatorial complexity of its Voronoi diagram. In the Euclidean case, the known lower bound is quadratic in the number of input objects, while the upper bound is essentially cubic. The complexity is conjectured to be nearly quadratic.

Background and progress

The origin of the problem is uncertain. Let $n\in\mathbb{N}$ denote the number of input lines or line segments. For the Euclidean case, the reported bounds leave a gap between a lower bound of $\Omega(n^2)$ and an essentially cubic upper bound [Sharir, 1994]. Under polyhedral distance functions, the complexity is quadratic [Boissonnat et al., 1998].

Related progress concerns the level sets of the Voronoi diagram of lines. These level sets are given by the union of a set of cylinders, and their complexity is near-quadratic [Agarwal and Sharir, 2000]. The full Voronoi-diagram problem remains open and is conjectured to have nearly quadratic complexity. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p3.

Reference papers

Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensionsPankaj K. Agarwal, Micha SharirDiscrete Comput. Geom. · 2000
Voronoi diagrams in higher dimensions under certain polyhedral distance functionsJean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, Mariette YvinecDiscrete Comput. Geom. · 1998
Almost tight upper bounds for lower envelopes in higher dimensionsMicha SharirDiscrete Comput. Geom. · 1994

Voronoi Diagram of Lines in 3D

Coming soon

Organizer