PaperlayerView exact revision on arXiv

Source-linked AI summary

Quadratic Complexity of Voronoi Diagrams in $\mathbb{R}^3$ for Lines in a Single Ruling of a Regulus

Eunku Park

arXiv:2608.27114v1cs.CGmath.AG

TL;DR

The paper asks whether Voronoi diagrams of lines in a structured ruling class can have quadratic rather than near-cubic complexity. It uses a Plücker-conic representation and quartic sphere-contact analysis to prove matching quadratic bounds, construct quadratic nearest complexity, and enumerate vertices in quadratic time.

  • Problem

    For arbitrary lines in R^3, nearest Voronoi-diagram complexity is known only between Ω(n^2) and O(n^{3+ε}).

  • Method

    The paper represents the ruling as a Plücker plane conic, restricts sphere tangency to a binary quartic, and uses root sign patterns to enumerate support types and vertices.

  • Results

    The nearest diagram has worst-case complexity Θ(n^2), the farthest diagram has Θ(n^2) complexity for every general-position input, and all finite vertices can be enumerated in O(n^2) time.

  • Takeaways & Limitations

    One ruling of a smooth regulus is a geometrically invariant line class with exact quadratic worst-case Voronoi complexity despite continuously varying line directions.

  • Takeaways & Limitations

    The result is restricted to lines in one ruling of a smooth regulus, while broader structured line families and the arbitrary-line bound remain open directions.

Abstract

from arXiv · show

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 general-position set of $n$ lines with at least $(n-2)(n-3)/2$ distinct regular nearest vertices, where regular means that exactly four lines support the vertex and their three defining bisectors meet transversely. Thus the worst-case complexity of the nearest Voronoi diagram in this class is $Θ(n^2)$, while the farthest diagram has $Θ(n^2)$ complexity for every general-position input, since it has exactly $n(n-1)$ three-dimensional cells. Under the Plücker embedding, the ruling is a conic, and the condition for a line to be tangent to a Euclidean sphere restricts to a binary quartic. At a regular vertex, the four supporting parameters exhaust its roots, and sign alternation forces two arcs of the parameter circle to be site-free. This leaves only $n(n-3)/2$ possible cyclic support types, while Bézout's theorem bounds the number of centers for each type by eight. The same reduction yields an exact $O(n^2)$-time algorithm that, after cyclically sorting the site parameters, enumerates all finite nearest and farthest vertices as constant-degree real univariate representations.

1 Introduction

The paper resolves the complexity order for nearest and farthest Voronoi diagrams of lines drawn from one ruling of a smooth regulus, using a Plücker-conic and quartic-contact reduction.

  • Motivation: The arbitrary-line nearest-diagram problem remains open, with known bounds Ω(n^2) and O(n^{3+ε}).The paper studies a structured ruling class to narrow this gap.
  • Input class: Lines in one ruling form a continuous one-parameter family of pairwise skew lines with continuously varying directions.The class includes rulings of one-sheeted hyperboloids and hyperbolic paraboloids.
  • Proof strategy: A ruling becomes a plane conic under the Plücker embedding, while sphere tangency restricts to a binary quartic on its parameter circle.At regular vertices, four supporting parameters exhaust the quartic roots; sign alternation leaves two site-free arcs.
  • Upper bounds: The nearest and farthest diagrams each have at most 4n(n−3) vertices and O(n^2) total combinatorial complexity under general-position assumptions.The upper bounds apply to n≥4 affine lines in one ruling of a smooth quadric.
  • Proof strategy: Only n(n−3)/2 cyclic support types remain, and Bézout bounds each type by eight possible centers.This yields the quadratic nearest-vertex upper bound; the analogous sign argument gives the farthest bound.
  • Lower bound and algorithm: The construction gives (n−2)(n−3)/2 distinct regular nearest vertices on a fixed non-rotational hyperboloid, while the structural proof yields an O(n^2)-time enumeration algorithm.After cyclic sorting, the algorithm solves n(n−3)/2 systems of three quadratic equations in three variables.

2 Preliminaries

The paper represents lines projectively with Plücker coordinates and models a ruling of a smooth split real quadric as a conic. It imposes general-position conditions and recalls combinatorial relations linking vertices to total Voronoi complexity.

  • Plücker coordinates and ruling conics: Plücker coordinates identify projective lines with points on the Klein quadric, while metric calculations use vector–moment coordinates (v, m).The moment is m = a × v, and the coordinates satisfy the Plücker relation.
  • Plücker coordinates and ruling conics: Each ruling of a smooth split real quadric is a nonsingular plane conic with a reduced homogeneous quadratic parametrization.The two families consist of projective lines; distinct lines in one ruling are skew as affine lines.
  • General position: The general-position assumptions require pairwise skew lines, exclude selected coplanar or fivefold sphere tangencies, and prevent a sphere-contact form from vanishing on the entire ruling.The final condition specifically excludes a sphere tangent to every generator of the ruling.
  • Combinatorial relations: The nearest diagram satisfies EN = 2VN + 2n −2, FN = VN + 3n −3, and CN = n under the stated assumptions.These relations convert nearest-vertex bounds into total combinatorial complexity bounds.
  • Combinatorial relations: The farthest diagram satisfies EF = 2VF + n^2 −n −2, FF = VF + 2n^2 −2n −3, and CF = n^2 −n.The cell count supplies a quadratic lower bound for farthest-diagram complexity.

3 The Contact Quartic and Quadratic Upper Bounds

Restricting the line–sphere tangency condition to the ruling conic produces a binary quartic whose alternating signs constrain supports to quadratically many cyclic gap pairs. Bézout bounds each pair’s centers, yielding quadratic vertex and total-complexity bounds.

  • 3.1 The contact quartic: A sphere’s tangency condition becomes a homogeneous binary quartic Hc,R on the ruling’s projective parameter circle.The original condition is quadratic in Plücker coordinates, and the ruling parametrization is quadratic, giving degree four.
  • 3.1 The contact quartic: Four distinct tangencies exhaust the quartic’s projective roots, which are simple, and the sign alternates across its four complementary arcs.This root structure is the basis for identifying empty arcs for nearest and farthest vertices.
  • 3.2 Cyclic supports: Nearest supports are endpoints of two disjoint negative-sign cyclic gaps, whereas farthest supports are endpoints of two disjoint positive-sign cyclic gaps.Nearest-ball emptiness forces nonnegative values at all site parameters; the farthest condition analogously forces nonpositive values.
  • 3.3 Quadratic upper bounds: A fixed quadruple supports at most eight regular real Voronoi vertices because three quadratic equal-distance equations have Bézout bound 2^3 = 8.Regular vertices are isolated simple real solutions of these equations.
  • 3.3 Quadratic upper bounds: VN ≤ 4n(n −3) and VF ≤ 4n(n −3), and both diagrams therefore have O(n^2) total combinatorial complexity.The vertex bounds combine n(n −3)/2 support pairs with at most eight centers per pair; the cited combinatorial identities convert vertices to total complexity.
  • 3.3 Quadratic upper bounds: The farthest diagram has an Ω(n^2) lower bound from CF = n^2 −n, while a separate construction is needed for a nearest-diagram lower bound.The farthest lower bound does not assert quadratically many finite vertices.

4 A Lower Bound on a Fixed Ruling

The paper constructs quadratically many distinct regular nearest Voronoi vertices on one ruling of a fixed non-rotational one-sheeted hyperboloid. The construction realizes suitable contact quartics by nearby spheres and ensures general position and transversality.

  • Local realization: The contact polynomial at the base sphere has fourth-order contact at u = 0, providing a base point for realizing nearby quartics.The polynomial is Pc∗,R∗(u) = 40u4, and the degenerate contact supports local realization.
  • Local realization: The coefficient map is locally invertible because det DΨ(c∗, R∗) = 1 250̸ = 0.The inverse function theorem then realizes every nearby monic quartic with positive squared radius and leading coefficient.
  • Empty supporting spheres: For sufficiently close site parameters, each constructed sphere is tangent to four selected lines and its open ball meets no input line.The quartic is negative exactly on the two selected consecutive-site gaps and positive at every non-support parameter.
  • Regularity and general position: The site parameters can be chosen so all construction spheres determine regular nearest vertices while satisfying the general-position assumptions.The supporting points are affinely independent, and the three bisectors meet transversely.
  • Lower-bound construction: A fixed hyperboloid ruling contains a general-position set with at least (n −2)(n −3)/2 distinct regular nearest Voronoi vertices.Every admissible index pair yields an empty transverse supporting sphere, and distinct pairs produce distinct centers.
  • Conclusion: Combining the quadratic upper bound with this construction gives worst-case nearest-diagram complexity Θ(n^2).The upper bound is supplied by the general vertex bound, while each regular vertex is a distinct combinatorial feature.

5 Enumerating Voronoi Vertices

The enumeration algorithm reduces candidate supports to cyclically disjoint gap pairs, solves constant-size quadratic systems, and certifies candidates by contact-quartic signs. Under the stated real-RAM model, it enumerates all finite nearest and farthest vertices in O(n^2) time.

  • Candidate generation: The algorithm enumerates all unordered pairs of vertex-disjoint cyclic gaps after sorting the site parameters.There are exactly n(n −3)/2 such pairs, and a reduced parametrization is assumed as input.
  • Candidate generation: Each gap pair produces a system of three quadratic equations in three variables for common equidistant centers.Each system has constant description complexity and at most eight isolated real solutions.
  • Certification: Candidates are rejected unless the contact quartic is nonzero, has four simple support roots, and satisfies transversality.The sign pattern on the four arcs then classifies a candidate as nearest or farthest.
  • Correctness: The algorithm reports exactly the finite vertices of both diagrams without duplicates within either diagram.Completeness follows because every regular vertex supplies a pair of vertex-disjoint gaps; sign tests certify emptiness or containment.
  • Complexity: After O(n log n) sorting, simultaneous nearest-and-farthest vertex enumeration takes O(n^2) time in the real-RAM model.The algorithm solves exactly n(n −3)/2 systems and performs O(n^2) additional arithmetic, rank, and sign operations.
  • Optimality: The nearest-vertex enumeration algorithm is worst-case optimal up to a constant factor.Some inputs have Ω(n^2) distinct nearest vertices, so explicit reporting requires Ω(n^2) time.

6 Conclusion

Restricting line sites to one ruling of a smooth regulus yields exact quadratic worst-case complexity for both nearest and farthest Voronoi diagrams. The quartic contact reduction is the decisive mechanism, while broader structured classes remain open.

  • Main conclusion: Nearest and farthest Voronoi diagrams for lines in one ruling have quadratic combinatorial complexity under the stated assumptions.The nearest diagram has Θ(n^2) worst-case complexity, and every general-position farthest diagram has Θ(n^2) complexity.
  • Main conclusion: The nearest Θ(n^2) bound combines an O(n^2) upper bound with a construction having Ω(n^2) vertices.For farthest diagrams, the n^2 −n three-dimensional cells provide a quadratic lower bound for every admissible input.
  • Proof mechanism: Restricting sphere contact to the ruling conic produces a quartic whose four roots and sign alternation reduce possible support quadruples from Θ(n^4) to Θ(n^2).Two complete arcs of the parameter circle must be site-free.
  • Open direction: Future work is to identify broader natural line families whose nearest diagrams also have Θ(n^2) worst-case complexity.The paper does not determine which geometric or algebraic properties force both quadratic upper and lower bounds.

A Explicit Rulings of Standard Doubly Ruled Quadrics

The appendix gives explicit rulings for standard doubly ruled quadrics, verifies their incidence properties, and develops polynomial vector–moment parametrizations for the fixed hyperboloid used in the lower-bound construction.

  • One-sheeted hyperboloid: The one-sheeted hyperboloid has two rulings whose distinct affine lines within the same ruling are skew.Their direction vectors are nonparallel, so distinct lines in either family are skew.
  • One-sheeted hyperboloid: Every affine point of the hyperboloid belongs to exactly one line from each ruling.Lines from opposite rulings meet in the projective closure, including at a common point at infinity when affine lines are parallel.
  • Hyperbolic paraboloid: The hyperbolic paraboloid likewise has two affine generator families, with same-family lines skew and opposite-family lines intersecting once.The parametrization uses u = x −y and v = x + y to express the surface equation z = (x −y)(x + y).
  • Projective closure: The projective closure adds two generator lines at infinity, which are excluded because they have no affine points.The affine families therefore provide precisely the line sites available for the Euclidean Voronoi diagrams.
  • Polynomial parametrization: For the fixed hyperboloid, a half-angle substitution yields polynomial vector–moment data V(u) and M(u) satisfying V(u) · M(u) = 0.Multiplication by the positive factor 1 + u2 produces the polynomial parametrization used in the algebraic construction.

B.3 Regularity and transversality

The section establishes that nonsingularity of the evaluation map transfers to regularity of the four-line Voronoi vertex: affine-independent contacts yield transversely intersecting bisectors.

  • The four tangency equations are encoded by functions F_k(c, R) = d(c, ℓ_{r_k})^2 − R for the four selected lines.
  • At a common zero, differentiating the four functions produces a factorization involving the quartic-root evaluations and a Vandermonde matrix.
  • The evaluation Jacobian is nonsingular throughout a sufficiently small inverse-function neighborhood.
  • The tangency Jacobian is nonsingular exactly when the four contact points are affinely independent.
  • The same rank argument makes the three bisectors transverse, so an empty common tangent sphere defines a regular nearest Voronoi vertex.

B.4 Excluding tangency to the entire ruling

The section rules out spheres tangent to the entire chosen ruling, ensuring that a contact quartic is nonzero and therefore cannot vanish at five distinct ruling parameters.

  • For every λ > 1, no real Euclidean sphere is tangent to every generator of the chosen ruling.
  • Assuming universal tangency forces algebraic relations among the sphere center coordinates and squared radius.
  • When YZ ≠ 0, the relations imply Y^2 = −2(λ^2 − 1), which has no real solution for λ > 1.
  • When YZ = 0, the relations force X = Y = Z = 0, while the coefficient equations require contradictory radius values.
  • Because a nonzero contact quartic has degree four, no real sphere can be tangent to five distinct lines of the ruling.

B.5 Genericity of the site parameters

Generic site parameters are chosen by excluding proper algebraic exceptional sets while preserving local quartic realizations, producing simultaneously regular nearest and farthest vertices and enabling parameter recovery and sorting.

  • Distinct lines in one ruling are pairwise skew, and any three direction vectors are linearly independent, preventing three sites from being parallel to a common plane.
  • The complexified coefficient map is generically finite because its source and target both have dimension four and its Jacobian is nonzero at a suitable point.
  • For each ordered root quadruple, the Vieta map is locally invertible, so exceptional coefficient values pull back to proper algebraic subsets with empty interior.
  • The normalized direction curve lies on no circle, so cocircular direction representatives occur only on a proper algebraic subset.
  • Choosing parameters outside the finite union of exceptional subsets gives general position within a nonempty ordered simplex.
  • For every admissible gap pair, the constructed sphere is transverse, empty of non-support lines, and determines a regular nearest vertex; positive arcs analogously yield farthest vertices.
  • A ruling conic and rational parametrization can be recovered in O(n) time, after which site parameters are cyclically sorted in O(n log n) time.
  • Each regular vertex uniquely determines its two sign-selected gaps, preventing duplicate reporting within either diagram.

C.3 Real-RAM running time and storage

The running-time analysis shows that gap-pair enumeration and constant-degree candidate certification yield quadratic time, with linear working storage when output is streamed.

  • The algorithm creates one constant-description-complexity system of three quadratic equations in three variables for each gap pair.
  • Each system has at most eight isolated real solutions, all obtainable in O(1) real-RAM time.
  • Candidate certification uses constant-size tests for radius, quartic nonzeroness, simple roots, bisector-gradient rank, and arc signs.
  • 4n(n − 3) candidates require O(n^2) total solving and certification time, while the same candidate set serves both diagrams.
  • Streaming certified vertices uses O(n) working storage excluding output; storing all vertices can require O(n^2).

C.4 Real-RAM convention and bit complexity

The analysis uses a real-RAM model with constant-time bounded-degree algebraic primitives, yielding O(n^2) gap-pair processing. A bit-model implementation instead incurs polynomial dependence on input representation size.

  • Real-RAM convention: Constant-size bounded-degree polynomial systems, exact real-algebraic representations, and sign tests are treated as constant-time operations in the real-RAM model.These primitives include solving systems, storing isolated solutions, and evaluating bounded-degree polynomial signs.
  • Real-RAM convention: O(n^2) follows because every gap pair satisfies the fixed-dimension and fixed-degree requirements and is processed in O(1) time.The cyclic-order comparisons are absorbed into the stated bound for n ≥4.
  • Bit complexity: Exact bit-model implementations represent isolated solutions by real univariate representations and use root isolation and sign determination for the required tests.Fixed dimension and degree keep the representation degrees bounded by an absolute constant.
  • Bit complexity: For rational inputs of bit length at most Bin, elimination, root isolation, and sign determination require poly(Bin) bit operations per gap pair.The total bit complexity also includes writing the exact output representations.
  • Bit complexity: The O(n^2) real-RAM running-time analysis excludes dependencies on the degrees and bit lengths of real-algebraic input representations.An analogous bound holds with polynomial dependence on those representation parameters.
Loading 2608.27114v1…