PaperlayerView exact revision on arXiv

Source-linked AI summary

A Collapse Process for Farthest Voronoi Diagrams of Lines in Three Dimensions

Evanthia Papadopoulou, Martin Suderland, Zeyu Wang

arXiv:2609.29865v1cs.CG

TL;DR

Constructing the 3D farthest Voronoi diagram of lines remains challenging. This paper uses a collapse process to classify its shrinking-map events and gives geometric criteria for vertex events and trisector extrema. It proves the event list is complete and tightly bounds the number of trisector extrema.

  • Problem

    The Euclidean Voronoi diagram of lines and other generalized sites in 3D remains challenging, with a complexity gap between Ω(n^2) and O(n^(3+ε)).

    Source: §1 · p. 2

  • Method

    The collapse process starts from the unbounded features and sweeps inward, classifying changes to the shrinking map, including vertex events by tangent-point hulls.

    Source: §1 · pp. 2–3

  • Results

    Four non-terminal event types and one terminal event complete the classification; trisector distance has at most 4 local maxima and 8 local minima, both bounds tight.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    A vertex’s event type follows from its four tangent points’ spherical hull, and trisector minima provide a direct method to find the smallest sphere tangent to three lines.

    Source: §1 · p. 3

    The algorithm retains an additional dependence on kmax; removing it in an output-sensitive algorithm is left for future work.

    Source: §6.3 · p. 14

Abstract

from arXiv · show

We study a \emph{collapse process} to construct the farthest Voronoi diagram of lines in three dimensions, given a spherical map of the diagram's unbounded features. The collapse process sweeps through the diagram in order of decreasing distance from the farthest lines. It follows the \emph{shrinking map}, a cell complex on a topological sphere that encodes the locus of points with a fixed farthest distance. We show that, in three dimensions, the collapse process has exactly four non-terminal local event types that change the structure of the shrinking map: \emph{deletion, swap, local minimum}, and \emph{local maximum} events; plus one terminal event. This list is complete. We give intrinsic three-dimensional geometric descriptions of the four non-terminal events. First, we classify the two vertex-related events, deletion and swap events, by the spherical convex hull of the four tangent points from a vertex to its four defining lines. Then, we analyze the events related to the local extrema of the distance function along the trisector of three lines. We show that the distance function along a trisector has at most $4$ local maxima and $8$ local minima, and that both bounds are tight. The extrema can be found via a polynomial of degree $12$. As a byproduct, this gives a direct method for finding the smallest sphere tangent to three given lines. At each local extremum, the tangent sphere touches the three lines at points lying on a great circle. The collapse process and the completeness of the event list also apply, under similar general position assumptions, to the farthest Voronoi diagram of convex sites under strictly convex distance functions.

1 Introduction

The paper develops a collapse process for constructing the 3D farthest Voronoi diagram of lines from its unbounded features. It classifies every shrinking-map event and gives geometric criteria for vertex events and trisector extrema.

1 Introduction

  • In 3D, Euclidean Voronoi diagrams of lines and other generalized sites remain challenging; the well-known complexity gap for lines spans from Ω(n^2) to O(n^(3+ε)).Source: §1 · p. 2
  • The collapse process starts from the diagram’s unbounded features and sweeps inward, maintaining an active front to discover the diagram.The unbounded features are encoded by a spherical map, and the shrinking map represents equal-priority points during the sweep.Source: §1 · p. 2
  • The shrinking map has exactly four non-terminal event types—deletion, swap, local minimum, and local maximum—plus one terminal event; the list is complete.Deletion and swap occur at Voronoi vertices; the extrema events occur along trisectors.Source: §1 · p. 2
  • A vertex is a deletion event when its four tangent points have a spherical-triangle hull, and a swap event when their hull is a quadrilateral.This gives a purely three-dimensional criterion instead of a four-dimensional upper-envelope viewpoint.Source: §1 · p. 3
  • A trisector distance has at most 4 local maxima and 8 local minima, both tight; its extrema are computable by a degree-12 polynomial.At each extremum, the tangent sphere touches the three lines at points on a great circle; choosing the smallest local minimum gives the smallest sphere tangent to three lines.Source: §1 · p. 3
  • After initialization, the algorithm runs in O(|FVD(L)| kmax log n); brute-force initialization can take quadratic time in the unbounded faces bounding each cell.Here kmax is the maximum face size encountered during collapse.Source: §1 · p. 3
  • The collapse viewpoint and complete event list also extend to convex sites under convex distance functions.The paper describes this extension under similar general-position assumptions.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the farthest Voronoi diagram and its sectors, state the general-position assumptions, and describe spherical maps for encoding unbounded features.

2 Preliminaries

  • The farthest Voronoi diagram partitions space into regions where each point is farther from its region’s line than from every other line.The region definition uses strict inequality.Source: §2 · p. 3
  • Points equidistant from k lines form a k-sector of dimension 4−k; 2-sectors are bisectors and 3-sectors are trisectors.Two trisectors are related when they involve exactly four distinct lines.Source: §2 · p. 3
  • The general-position assumptions exclude specified parallel, coplanar-tangency, five-line tangency, and cocircular-direction cases.They imply that Voronoi vertices meet four edges and related trisectors intersect transversely.Source: §2 · p. 3
  • The Gaussian map encodes cells’ unbounded directions on the unit sphere and has O(n^2) complexity and construction time for this diagram.Source: §2 · p. 3
  • The Γ-map is the diagram’s intersection with a sufficiently large boundary sphere, and the Gaussian map is its limit as the sphere’s radius grows.The Γ-map can be constructed from the Gaussian map.Source: §2 · pp. 3–4
  • From a point in a line’s farthest region, the ray through its closest point on that line stays in the region, with distance strictly increasing.Source: §2 · p. 4
  • Every 3D cell is unbounded, and each line’s farthest Voronoi region has exactly n−1 3D cells.Source: §2 · p. 4

3 The Collapse Process and Five Event Types

The collapse process sweeps downward through distance levels, representing each level set as a labelled shrinking map on a sphere. Under general position, its structure changes only at four non-terminal event types and one terminal event.

3 The Collapse Process and Five Event Types

  • For every priority above the global minimum, the shrinking map is a topological sphere; below it, the map is empty.At sufficiently large priority, it is equivalent to the Γ-map, from which the process starts.Source: §3 · p. 4

3.1 Events of the Collapse Process

  • The four non-terminal events are deletion, swap, local minimum, and local maximum; a terminal event completes the list.Deletion and swap occur at Voronoi vertices; the two local-extremum events occur along trisectors.Source: §3.1 · pp. 4–5
  • Between consecutive event priorities, the shrinking map remains combinatorially unchanged, and every event is one of the five listed types.The terminal event shrinks two faces simultaneously and leaves the map empty.Source: §3.1 · p. 5

3.2 Completeness of the Event List

  • A terminal event, if it occurs, is last and corresponds to a global minimum of the common distance on a bisector.It occurs at half the distance between the two defining lines.Source: §3.2 · p. 6
  • A face cannot disappear with four or more neighboring faces under general position; disappearance with three, two, or one neighbor corresponds to deletion, local minimum, or terminal events.A proposed touch event is also excluded because it would make two related trisectors intersect tangentially, contrary to general position.Source: §3.2 · p. 7
  • When no face disappears but an adjacency changes, the old adjacency is replaced by a new one in a swap event.The proof also establishes that holes in a component are already present at the larger priority.Source: §3.2 · pp. 6–7

4 Intrinsic Classification of Vertex Events

The paper classifies four-line Voronoi vertices using the spherical hull of their four tangent points. It also gives a local test for distinguishing vertex types from the orientations of incident trisectors.

4 Intrinsic Classification of Vertex Events

  • The spherical-hull criterion gives a three-dimensional geometric classification in place of distinguishing these events through the upper envelope in four dimensions.The paper also presents the hull test as a purely three-dimensional criterion.Source: §4 · p. 7
  • At a vertex, the derivative of common distance along an oriented trisector is the dot product of its line-distance gradient with the trisector tangent.The positive local arc is the direction in which common distance increases.Source: §4 · p. 7
  • The positive side of each incident trisector belongs to the four-line farthest Voronoi diagram exactly under its corresponding determinant-sign condition.The test uses the determinant combination η and the determinants of triples of line-distance gradients.Source: §4 · p. 7
  • Three satisfied side-test conditions identify a deletion vertex, whereas two identify a swap vertex.Equivalently, the displayed product of determinants is positive for a swap and negative for a deletion.Source: §4 · p. 8
  • A vertex is a deletion vertex when its four tangent points have a spherical triangular hull, and a swap vertex when their hull is a spherical quadrilateral.The tangent points lie on the sphere centered at the vertex, since the vertex is equidistant from its four defining lines.Source: §4 · p. 8
  • In the trisector illustration, color encodes distance, and the middle branch’s orange-yellow-orange transition marks a local maximum.The maximum’s position is highlighted in the figure.Source: Figure 4 · p. 9

5 Local Extrema on Trisectors

The section analyzes local extrema of the common distance function along a three-line trisector, establishing tight bounds, a degree-12 computation, and a geometric characterization of extrema.

5 Local Extrema on Trisectors

  • Local minima and maxima of the common distance along a trisector correspond to local minimum and maximum events in the collapse process.Source: §5 · p. 9
  • There are at most 4 local maxima and 8 local minima on a three-line trisector, and both bounds are tight.The four unbounded branches have at most 12 critical points total; an example attains 8 minima and 4 maxima.Source: §5 · pp. 9–10, Figure 5 · p. 10
  • The smallest sphere tangent to three given lines is found by selecting the minimum-distance local minimum along their trisector.The distance tends to infinity at every unbounded end, so its global minimum is attained at a local minimum.Source: §5 · p. 10
  • A degree-12 polynomial computation finds the extrema by solving for critical points on the projected trisector.The projected trisector satisfies P=0; constrained criticality gives P=0 and Q=0, whose resultant has degree 12.Source: §5 · pp. 9–10
  • At each local extremum, the tangent sphere touches the three lines at points lying on a common great circle.The unit directions from the center to the closest points lie in a plane through the origin.Source: §5 · pp. 10–11

6 Algorithmic Outlook and Related Aspects

The paper constructs the initial Γ-map, derives structural consequences of the collapse process, and outlines an algorithm and a generalization to convex sites. The analysis bounds diagram complexity and identifies both runtime dependencies and the results that extend to the generalized setting.

6.1 Constructing the Γ-map from the Gaussian Map

  • Resolving Gaussian-map vertices of anomaly yields Γ(FVD(L)) in O(n^2) time, preserving the correct topology by removing the anomalous vertices and reconnecting boundaries.For each pair of vertices, the farther line determines which incident faces are merged.Source: §6.1 · pp. 11–12

6.2 Consequences for the Farthest Voronoi Diagram

  • The farthest Voronoi diagram has complexity Θ(n^2 + n_s + n_M), where n_s and n_M count swap and local-maximum events.The event counts satisfy n_d + n_m − n_M = n^2 − n − 2·1_d, with 1_d indicating whether the process ends with a non-deletion event.Source: §6.2 · p. 12
  • A local-maximum event splits one shrinking-map face into two distinct faces.The event’s face split is also used to rule out holes in cells during the collapse process.Source: §6.2 · p. 12
  • Every 3D cell has no holes, so its intersection with any sufficiently large ball is a topological 3-ball.The proof rules out holes by tracing the cell’s face through the collapse process and using the no-tunnel property.Source: §6.2 · p. 13

6.3 Algorithmic Outlook

  • Crossing local-maximum events cannot both occur: after the higher-priority event splits a face, the lower-priority event cannot happen.The algorithm maintains a size-|f| bucket of possible local maxima for each face and updates it when neighboring events change that face.Source: §6.3 · p. 13
  • The algorithm generates local-maximum events on the fly and runs in O(|FVD(L)| k_max log n) plus initialization time.Brute-force initialization takes time proportional to the sum of squared face sizes in Γ(FVD(L)); removing the k_max dependence is left for future work.Source: §6.3 · p. 14

6.4 Generalization to Convex Sites under a Convex Distance Function

  • For a set S of n disjoint convex sites in R3 and the more universal distance dC defined using a bounded strictly convex set C ⊂ R3, results 3, 4, 8–10, 17, 19, and 21 still hold.Source: §6.4 · p. 14
Loading 2609.29865v1…