Voronoi Diagram of Lines in 3D

Definitions and mathematical statement

Let $\mathcal S=\{s_1,\ldots,s_n\}$ be straight lines in $\mathbb R^3$, or, in the segment version, closed nondegenerate line segments. For $x\in\mathbb R^3$ put $d(x,s)=\inf_{y\in s}\|x-y\|_2$. The Voronoi cell of site $s_i$ is \[ V_i=\{x:d(x,s_i)\le d(x,s_j)\text{ for every }j\}. \] The diagram is the subdivision by nearest-site sets. Its combinatorial complexity counts connected faces of dimensions zero through three, including disconnected pieces with the same nearest-site label. One may use inputs in general position so that coincident bisectors and nongeneric higher-order ties do not make the count ambiguous.

Determine the largest possible complexity as a function of $n$ for each of the line and segment versions. The principal conjectural target is near-quadratic complexity: for every fixed $\varepsilon>0$, an upper bound $O_\varepsilon(n^{2+\varepsilon})$, together with sharp lower constructions. The distance is Euclidean distance to the whole site, not distance to a chosen endpoint or to an intersection with a fixed plane. Bounds only for a single distance level set do not automatically bound the full three-dimensional diagram.

Short English statement

How complicated can the nearest-line or nearest-segment subdivision of three-dimensional space be? Is its worst-case size nearly quadratic?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500003 (AMR-054-0003), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 3. Original source indexed by AMR-054-0003. https://topp.openproblem.net/p3.