{"id":"arxiv/2608.27114","url":"https://arxiv.org/abs/2608.27114","tags":["cs.CG","math.AG"],"score":0,"title":"Quadratic Complexity of Voronoi Diagrams in $\\mathbb{R}^3$ for Lines in a Single Ruling of a Regulus","domain":"cs.CG","source":"arxiv","authors":["Eunku Park"],"reviews":0,"subject":"cs.CG","summary":"We study nearest and farthest Voronoi diagrams of lines in $\\mathbb{R}^3$ under the Euclidean metric when all $n$ lines belong to one ruling of a smooth doubly ruled real quadric. For arbitrary line sites, the combinatorial complexity of the nearest Voronoi diagram is known only to lie between $Ω(n^2)$ and $O(n^{3+\\varepsilon})$. Under general-position assumptions, we prove that both diagrams in the ruling class have at most $4n(n-3)$ vertices and $O(n^2)$ total combinatorial complexity. Conversely, for every $n \\ge 4$, one ruling of a fixed non-rotational one-sheeted hyperboloid contains a…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-27","reactions":{}}