Quadratic Complexity of Voronoi Diagrams in ℝ3 for Lines in a Single Ruling of a Regulus
Abstract
We study nearest and farthest Voronoi diagrams of lines in three-dimensional Euclidean space, which partition space according to the closest and farthest input lines, respectively. For arbitrary lines, a gap remains between the known quadratic lower bound and near-cubic upper bounds for the complexity of the nearest diagram. We consider input lines chosen from one of two continuous families of straight lines on a smooth surface defined by a quadratic equation, with one line from each family passing through every point of the surface. Under the geometric assumptions stated in the paper, we prove quadratic upper bounds on the total number of vertices, edges, faces, and connected three-dimensional regions in both diagrams. We also construct quadratically many nearest vertices using lines from a single family on one fixed surface, establishing a tight quadratic worst-case bound. The farthest diagram has quadratic total complexity for every input satisfying our assumptions. Our proof uses a parametrization that arranges the input lines in a cyclic order and expresses tangency to a sphere by a polynomial equation of degree four. At a Voronoi vertex, the four tangent input lines give four distinct roots. The sign changes between these roots, together with the nearest or farthest condition, force two intervening parameter intervals to contain no other input parameters. Thus, only quadratically many choices of four lines can define a vertex, and each choice yields at most eight isolated candidate centers.
Related
- Minkowski Tensors of Planar Anisotropic Voronoi Diagrams
- Motion planning and topological complexity for diagrams of spaces
- The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients
- A Quadratic Lower Bound on Determinantal Complexity
- Dynamic-Threshold Algorithms for the Continuous Quadratic Knapsack Problem: Reset Mechanisms and Complexity
BibTeX
@misc{park2026quadratic,
title = {{Quadratic Complexity of Voronoi Diagrams in $\mathbbR^3$ for Lines in a Single Ruling of a Regulus}},
author = {Eunku Park and Kangjin Han},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2608.27114},
eprint = {2608.27114},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27114},
}
RIS
TY - UNPB
TI - Quadratic Complexity of Voronoi Diagrams in ℝ^3 for Lines in a Single Ruling of a Regulus
AU - Eunku Park
AU - Kangjin Han
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2608.27114
UR - https://arxiv.org/abs/2608.27114
AB - We study nearest and farthest Voronoi diagrams of lines in three-dimensional Euclidean space, which partition space according to the closest and farthest input lines, respectively. For arbitrary lines, a gap remains between the known quadratic lower bound and near-cubic upper bounds for the complexity of the nearest diagram. We consider input lines chosen from one of two continuous families of straight lines on a smooth surface defined by a quadratic equation, with one line from each family passing through every point of the surface. Under the geometric assumptions stated in the paper, we prove quadratic upper bounds on the total number of vertices, edges, faces, and connected three-dimensional regions in both diagrams. We also construct quadratically many nearest vertices using lines from a single family on one fixed surface, establishing a tight quadratic worst-case bound. The farthest diagram has quadratic total complexity for every input satisfying our assumptions. Our proof uses a parametrization that arranges the input lines in a cyclic order and expresses tangency to a sphere by a polynomial equation of degree four. At a Voronoi vertex, the four tangent input lines give four distinct roots. The sign changes between these roots, together with the nearest or farthest condition, force two intervening parameter intervals to contain no other input parameters. Thus, only quadratically many choices of four lines can define a vertex, and each choice yields at most eight isolated candidate centers.
ER -