Quadratic Complexity of Voronoi Diagrams in R cubed for Lines in a Single Ruling of a Regulus

arXiv:2608.27114 · cs.CG, math.AG · Submitted 2026-08-27 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Quadratic Complexity of Voronoi Diagrams in R cubed for Lines in a Single Ruling of a Regulus".

Jane: Here's the gist of the paper. We study nearest and farthest Voronoi diagrams of lines in R3 under the Euclidean metric when all n lines belong to one ruling of a smooth doubly ruled real quadric This work determines the exact asymptotic order of the worst-case combinatorial complexity for this class Combinatorial Complexity Bounds The main result determines the exact asymptotic order of the worst-case combinatorial complexity for this class Specifically, for general-position assumptions, both diagrams in the ruling class have at most 4n(n − 3) vertices and O(n 2) total combinatorial complexity For every n ≥ 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 Consequently, the worst-case combinatorial complexity of the nearest Voronoi diagram in this class is Θ(n 2) The farthest diagram has Θ(n 2) total combinatorial complexity for every such input, since it has n squared − n three-dimensional cells

4, Theorem 5.12: already provide the lower bound Algebraic Reduction and Vertex Enumeration The proof exploits the representation of lines in projective line space Under the Plücker embedding, a ruling becomes a plane conic in the Klein quadric, while the condition for a line to be tangent to a fixed Euclidean sphere restricts to a binary quartic on the parameter circle of the ruling At a regular Voronoi vertex, the four supporting parameters exhaust its roots, and sign alternation forces two arcs between consecutive roots to contain no other site parameters This converts the geometric support condition into a cyclic combinatorial problem with only quadratically many candidates A quadratic vertex-enumeration algorithm is provided, which runs in O(n 2)-time in the real-RAM model Structural Proof Ingredients The proof has three main ingredients We first pass from the ambient Euclidean space to the projective parameter space of lines under the Plücker embedding, where a ruling is represented by a plane conic γ: P 1 → K We then restrict the quadratic line–sphere tangency condition to this conic, obtaining a quartic on the real parameter circle The sign pattern of this quartic restricts the possible supporting quadruples to quadratically many cyclic configurations, from which the vertex and total combinatorial complexity bounds follow Worst-Case Realization The worst-case lower bound is established by constructing quadratically many regular nearest vertices using one ruling of the fixed non-rotational one-sheeted hyperboloid Q∗: x 2/4 + y squared − z squared = 1 The construction involves choosing parameters u i such that every pair (i, j) gives an empty transverse supporting sphere and hence a regular nearest Voronoi vertex This leads to the conclusion that the worst-case combinatorial complexity of the nearest Voronoi diagram over generalposition sets of n lines in one ruling of a smooth regulus is max L comp(NVD(L)) = Θ(n 2) Algorithmic Efficiency The algorithm enumerates all finite nearest and farthest Voronoi vertices that runs in O(n 2) time in the real-RAM model This is achieved by generating the n(n − 3)/2 possible pairs of vertex-disjoint cyclic gaps and solving a system of three quadratic equations in three variables for each pair, which has at most eight isolated real solutions The total enumeration time is O(n 2), which dominates the O(n log n) sorting time The paper establishes quadratic combinatorial complexity bounds for the nearest and farthest Voronoi diagrams of lines contained in one ruling of a smooth regulus Although these results do not improve Sharir’s O(n 3+ε) upper bound for arbitrary line sites

14: , they identify a geometrically invariant class, for which the exact worst-case order is quadratic An important direction for future research is to identify natural classes of n lines in R3 for which the nearest Voronoi diagram has worst-case combinatorial complexity Θ(n 2) References

Paper summary: Tom: So, looking at "Quadratic Complexity of Voronoi Diagrams in R cubed for Lines in a Single Ruling of a Regulus," what’s the big picture takeaway? It establishes that for this very specific geometric setup—lines on one ruling of a regulus—the worst-case combinatorial complexity settles right at theta of n squared, which is an exact order.

Jane: For someone listening who isn't steeped in this geometry, what does theta of n squared actually mean in terms of performance? It means that the structural elements you have to deal with—the vertices and cells in these diagrams—grow at most as fast as the square of the number of lines, which is a very controlled growth rate.

Lu: The implication for representation learning is that when we are dealing with structured data where the underlying geometry has this kind of regularity, we can expect complexity that scales quadratically rather than potentially hitting higher polynomial bounds like n cubed.

Meng: From an engineering standpoint, knowing the exact complexity means I don't have to worry about a sudden jump in runtime when my input size doubles; I know exactly what the scaling behavior is for this class of sites <ref:2608.27114#pg1>.

Lalam: Lalam confirms that this result identifies a geometrically invariant class of lines where the exact worst-case order is quadratic, which is a significant classification achievement in computational geometry <ref:2608.27114#pg3>.

Tom: The authors also pointed out that while they didn't improve Sharir’s O of n cubed plus epsilon upper bound for arbitrary line sites <ref:2608.27114#pg1>, they successfully found this specific class where the exact worst-case order is quadratic.

Jane: So, the main contribution here is pinning down that exact quadratic complexity for this specific class, which helps us understand the limits of what we can expect from Voronoi diagrams in these structured settings.

Conclusion: Tom: So, we're wrapping up on this paper about the Voronoi diagrams of lines in R cubed that belong to just one ruling of a smooth regulus <ref:2608.27114#pg1>.

Jane: Basically, the authors are proving that for this specific geometric setup, whether you’re looking at the nearest or farthest diagram, the worst-case combinatorial complexity is exactly quadratic.

Lu: They determine that both diagrams have at most four n squared minus three n vertices and a total complexity of something like big O of n squared.

Meng: So what does that actually mean for deployment? It means we can predict the runtime scaling for these specific structures, which is better than just guessing.

Lalam: The paper shows how they reduced the complicated geometry problem into a quadratic enumeration problem using some clever math based on projective space and sphere tangency conditions.

Tom: I guess the core result is that this class of lines has a tight quadratic bound, which is super specific compared to more general line arrangements.

Jane: It's interesting because it’s not just another upper bound; they also established a lower bound by constructing specific inputs—using one ruling of a hyperboloid—that force that worst-case complexity to hit n squared.

Lu: That construction part is key because it proves the quadratic complexity isn't just theoretical; it's achievable in reality for this geometry.

Meng: I wonder if this holds up when we introduce noise or slight perturbations to those line positions, because my models don't like perfect structures.

Lalam: The result is quite solid for general position, and it gives us a clear mathematical target for analyzing these diagrams without needing to check every single line arrangement manually.

Tom: It’s a nice way to categorize the complexity of geometric problems; you get a very clean scaling law for this specific configuration.

Jane: And while it doesn't beat some other upper bounds for lines in R cubed, it identifies this specific class where the exact order is quadratic, which is a big win for understanding structure.

Meng: I think what’s important now is figuring out if we can actually use that n squared bound to design more efficient algorithms for finding these diagrams on real-world data.

Lalam: We can definitely explore that, because having an exact complexity order helps us build better tools and not just guess at performance.

Department of Liberal arts and Sciences, DGIST, Republic of Korea

cs.CG, math.AG

Submitted: 2026-08-27

Updated: 2026-11-03

Comments: Added a coauthor, more detailed explanations of algebraic geometry, and additional figures

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 88/100

The gist: We study nearest and farthest Voronoi diagrams of lines in R3 under the Euclidean metric when all n lines belong to one ruling of a smooth doubly ruled real quadric.

Key concepts

Voronoi Diagram of Lines
This diagram partitions space based on which line is closest or farthest from a given point. In this study, we are looking at how the arrangement of lines in a specific family (a ruling) affects the complexity of these diagrams.
Regulus Ruling
A regulus is a set of straight lines that form a doubly ruled surface, like an hyperboloid. A 'ruling' refers to one specific set of parallel or intersecting lines within that surface. The paper focuses on lines belonging to just one such ruling.
Plücker Embedding
This is a mathematical technique used to represent lines in 3D space using points in a higher-dimensional projective space. It allows the geometric problem of line arrangements to be translated into algebraic problems involving plane conics, simplifying the analysis.
Combinatorial Complexity
This measures the total number of vertices and edges required to describe the Voronoi diagram. The result shows that for this specific class of lines, this complexity is bounded by O(n^2) in the worst case, meaning it grows quadratically with the number of lines.

Terminology

Summary

We study nearest and farthest Voronoi diagrams of lines in R3 under the Euclidean metric when all n lines belong to one ruling of a smooth doubly ruled real quadric. p. 0 The main result determines the exact asymptotic order of the worst-case combinatorial complexity for this class. p. 1

Combinatorial Complexity Bounds

The paper establishes quadratic combinatorial complexity bounds for both nearest and farthest Voronoi diagrams when lines belong to a single ruling of a smooth regulus. Specifically, the nearest Voronoi diagram has at most VN ≤ 4n(n−3) vertices and total combinatorial complexity comp(NVD(L)) = 4VN + 6n − 5 = O(n 2). p. 1 The farthest Voronoi diagram also has at most VF ≤ 4n(n−3) vertices and total combinatorial complexity comp(FVD(L)) = 4VF + 4n squared − 4n − 5 = O(n 2). p. 1 Furthermore, the worst-case combinatorial complexity of the nearest Voronoi diagram over generalposition sets of n lines in one ruling of a smooth regulus is Θ(n 2). p. 1

Algebraic-Geometric Reduction

The proof exploits the representation of lines in projective line space by passing from ambient Euclidean space to the projective parameter space of lines. Under the Plücker embedding, a ruling becomes a plane conic in the Klein quadric, while the condition for a line to be tangent to a fixed Euclidean sphere restricts to a binary quartic on the parameter circle of the ruling. p. 1 At a regular Voronoi vertex, the four supporting parameters exhaust its roots of this quartic, and sign alternation forces two arcs between consecutive roots to contain no other site parameters. p. 1 This reduces the number of possible supporting quadruples from O(n 4) to O(n 2). p. 3

Construction of Lower Bounds

The authors construct quadratically many regular nearest vertices using one ruling of the fixed non-rotational one-sheeted hyperboloid Q∗. This construction yields at least (n − 2)(n − 3)/2 distinct regular nearest vertices. p. 0 Consequently, the worst-case combinatorial complexity of the nearest Voronoi diagram over generalposition sets of n lines in one ruling of a smooth regulus is Θ(n 2). p. 1

Algorithmic Efficiency

The structural proof also provides a quadratic vertex-enumeration algorithm that runs in O(n 2) time in the real-RAM model. This algorithm enumerates all finite nearest and farthest vertices by solving n(n − 3)/2 systems of three quadratic equations in three variables and certifying candidates in O(1) time per pair. p. 2

General Position Conditions

The analysis relies on Assumption 4, which includes conditions such as the lines being pairwise skew and no sphere being tangent to four sites at four coplanar contact points. These conditions are crucial for ensuring that every four-site tangent sphere is an isolated regular point of a finite fiber. p. 8 The analysis also excludes cocircular direction representatives. p. 5

Conclusion and Future Directions

The work establishes quadratic combinatorial complexity bounds for the nearest and farthest Voronoi diagrams of lines contained in one ruling of a smooth regulus. The decisive property is that restricting the sphere-contact equation to the ruling conic produces a quartic, so four supporting lines exhaust its root budget and sign alternation forces two complete arcs of the parameter circle to be site-free. p. 0 p. 0 An important direction for future research is to identify natural classes of n lines in R3 for which the nearest Voronoi diagram has worst-case combinatorial complexity Θ(n 2). p. 1

Enumeration Details

The enumeration algorithm involves generating the possible supporting quadruples combinatorially and certifying the resulting algebraic candidates using their contact quartics. For each candidate, the algorithm performs constant-size computations including testing that Hx,R is nonzero and that the four support parameters are simple roots and determining the sign of Hx,R on its four complementary arcs. p. 6

Running Time Analysis

The total enumeration time is O(n 2) because there are exactly n(n − 3)/2 pairs of vertex-disjoint cyclic gaps. Each instance consists of three quadratic equations in three variables and has at most eight isolated real solutions. p. 2 Under the real-RAM convention, solving each system and certifying each candidate take O(1) time. p. 9

Vertex Certification

The algorithm reports exactly the finite vertices of NVD(L) and FVD(L), without duplicates within either diagram. For a regular nearest vertex, the selected gaps are exactly the two negative arcs of its contact quartic; for a regular farthest vertex, they are exactly the two positive arcs. p. 6 The sign test and Equation (11) certify that the open supporting ball meets no site line in the nearest case and that the closed supporting ball meets every site line in the farthest case. p. 6

Worst-Case Optimality

The O(n 2)-time nearest-vertex enumeration algorithm is worst-case optimal up to a constant factor in the real-RAM model. Different products Qij have different root sets, and local injectivity of the coefficient map gives different sphere parameters. p. 9 The condition that four direction representatives be cocircular is not identically satisfied. p. 5 p. 5

Input Representation

The input representation assumes a reduced rational Plücker parametrization γ: P 1−→ Γ of the ruling and the parameter τi in P 1(R) corresponding to each line. If only the Plücker coordinates of the lines are given, together with the promise that they belong to one ruling conic, then the conic, a rational parametrization, and the site parameters can be recovered in O(n) time. p. 9 The sorted parameter list requires O(n) storage. p. 9

Real-RAM Convention

The real-RAM convention treats the following operations as constant time whenever the numbers of variables and equations and their degrees are bounded by absolute constants. This includes computing the isolated real solutions of a polynomial system, storing such solutions by an exact real-algebraic representation, and determining the signs of bounded-degree polynomials at those solutions. p. 9 The O(n 2) running-time analysis in the real-RAM model does not account for these bit-size dependencies. p. 3

Bit Complexity

The total bit complexity is O(n squared poly(Bin)) in addition to the cost of writing the exact output representations. The O(n log n) comparisons used to determine the cyclic order are absorbed by this bound for n ≥ 4. p. 9 If input coefficients are rational and have bit length at most Bin, the total bit complexity is O(n squared poly(Bin)). p. 1 The O(n 3+ε) upper bound for arbitrary line sites remains between quadratic and near-cubic complexity. p. 0

Lower Bound Construction

The lower bound construction uses the fixed hyperboloid Q∗ when λ = 2. The sphere (c∗, R∗) has fourth-order contact with the ruling line corresponding to u = 0 and is used as a base point from which arbitrary nearby quartics can be realized. p. 7 This allows the realization of (n − 2)(n − 3)/2 distinct regular nearest Voronoi vertices. p. 0 The worst-case lower bound follows from its number of three-dimensional cells and does not assert quadratically many finite vertices. p. 7

Vertex Enumeration Algorithm

The algorithm generates the possible supporting quadruples combinatorially and certifies the resulting algebraic candidates using their contact quartics. The system of three quadratic equations in three variables has at most eight isolated real solutions. p. 2 For each candidate, the algorithm performs constant-size computations including solving the system and performing sign determinations. p. 3 The total enumeration time is O(n 2). p. 3

Geometric Interpretation of Regularity

The Jacobian for the four tangency equations factors into a nonsingular diagonal matrix times a Vandermonde matrix times DΨ. This is nonsingular for sufficiently small distinct roots, which is equivalent to affine independence of the four contact points and the three bisectors meeting transversely. p. 8 In particular, whenever the common tangent sphere is empty with respect to the input lines, its center is a regular nearest Voronoi vertex incident to the four corresponding nearest cells. p. 0

Exclusion of Degeneracies

Lemma 26 proves that for every λ > 1, no real Euclidean sphere is tangent to every line of the chosen ruling of Qλ: x 2λ2 + y squared − z squared = 1. This implies that no real sphere is tangent to five distinct lines of this ruling. p. 5 The condition that four direction representatives be cocircular is not identically satisfied.

Final Summary

The paper establishes quadratic combinatorial complexity bounds for both nearest and farthest Voronoi diagrams when lines belong to a single ruling of a smooth regulus. The worst-case combinatorial complexity of the nearest Voronoi diagram over generalposition sets of n lines in one ruling of a smooth regulus is Θ(n 2). p. 1 The farthest Voronoi diagram has a quadratic lower bound for every admissible input. p. 1 The decisive property is that restricting the sphere-contact equation to the ruling conic produces a quartic, so four supporting lines exhaust its root budget and sign alternation forces two complete arcs of the parameter circle to be site-free. The worst-case complexity for arbitrary lines remains between quadratic and near-cubic complexity. p. 3

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

1

No Voronoi diagram complexity is known for arbitrary lines in R 3; this paper establishes that for lines belonging to one ruling of a smooth regulus, both nearest and farthest Voronoi diagrams have total combinatorial complexity O(n 2). This allows AI systems to efficiently compute the exact number of vertices and cells in these specific geometric configurations.

2

AI systems can implement an O(n 2) time vertex enumeration algorithm in the real-RAM model by solving n(n - 3)/2 systems, each consisting of three quadratic equations in three variables. This provides a constructive method for finding all finite nearest and farthest Voronoi vertices for line sets constrained to a ruling.

3

The system can determine the nature of a vertex (nearest or farthest) by checking the sign pattern of the contact quartic Hc,R on its four complementary arcs. This test is efficient because one sign determination per arc suffices due to the properties derived from Assumption 4 and Theorem 6.

4

A worst-case lower bound for nearest Voronoi diagrams can be achieved by constructing instances with at least (n - 2)(n - 3)/2 distinct regular vertices. This provides a hard benchmark for testing the performance of new Voronoi diagram algorithms on structured line sets.

Sources

Related papers