Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

Sujoy Bhore, Sándor Kisfaludi-Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, Sampson Wong

TL;DR

This paper settles a nearly 30-year-old open problem in computational geometry by constructing Euclidean noncrossing Steiner $(1+\epsilon)$-spanners with $O(n/\epsilon^{3/2})$ edges. The authors provide a nearly matching lower bound of $\Omega(n/\epsilon^{3/2-\mu})$, demonstrating that their construction is essentially optimal in terms of how the number of edges scales with the precision parameter $\epsilon$.

What Problem Does This Paper Address?

In network design, a spanner is a subgraph that approximates the distances between points: for any two points, there must be a path in the spanner no longer than $(1+\epsilon)$ times their direct Euclidean distance.

In the plane, we often want these networks to be planar (noncrossing) to avoid physical interference or for algorithmic efficiency. However, a famous result shows that for some point sets (like the four corners of a square), you cannot achieve a stretch factor less than $\sqrt{2}$ without edges crossing. To get the stretch close to $1$, we must introduce Steiner points—extra vertices not in the original set that act as junctions.

The core challenge is sparsity: how many Steiner points and edges are required to maintain a $(1+\epsilon)$ stretch factor while keeping the graph planar? The previous best upper bound, established in 1996, was $O(n/\epsilon^4)$. This paper aims to close the gap between that loose bound and the known lower bounds.

Methods

The authors employ two distinct strategies for their upper and lower bounds:

The Upper Bound (Construction)

The authors improve upon a classic construction by Arikati et al. Their approach involves:

  1. Linear Transformations: Instead of using $O(1/\epsilon)$ rotated copies of the point set to approximate directions (the standard approach), they use only $O(1/\sqrt{\epsilon})$ carefully chosen affine transformations.
  2. Balanced Box Decomposition (BBD): In each transformed space, they use a BBD tree to partition the plane into "tiles." They then build a simple axis-parallel spanner within these tiles.
  3. Planarization: By overlaying these $O(1/\sqrt{\epsilon})$ planar graphs and adding Steiner points at every intersection, they create a final noncrossing graph. Because each individual graph is small and the number of graphs is reduced, the total number of intersections (Steiner points) drops significantly from $1/\epsilon^4$ to $1/\epsilon^{3/2}$.

The Lower Bound (Proof of Optimality)

To prove that $1/\epsilon^{3/2}$ is necessary, the authors turn to Geometric Measure Theory. They model spanner paths as "tubes" and use recent generalizations of the Szemerédi-Trotter theorem. While the original theorem counts incidences between points and lines, the new version counts intersections between "$\delta$-disks" and "$\delta$-tubes." This allows them to prove that any spanner with low stretch must contain many crossing paths, which, when made noncrossing, inevitably force a large number of Steiner points.

Datasets

As a theoretical paper in computational geometry, no external datasets were used. The results are proven for arbitrary sets of $n$ points in $\mathbb{R}^2$. For the lower bound, the authors construct a specific "worst-case" configuration consisting of two parallel rows of $n/2$ equally spaced points.

Key Insights and Ideas

  • The Power of $1/\sqrt{\epsilon}$: The most significant "aha moment" is realizing that the required angular resolution for a spanner is $\sqrt{\epsilon}$, not $\epsilon$. This square-root relationship is a recurring theme in high-precision geometry but was not fully exploited here until now.
  • Cone-Restricted Paths: The authors show that for a path to have length $\le 1+\epsilon$, every edge in that path must stay within a very narrow cone (angle $\approx \sqrt{\epsilon}$) relative to the destination.
  • Adventurous vs. Well-Behaved Paths: In the lower bound proof, they categorize paths. "Adventurous" paths (those that wiggle too much) are shown to be too long to satisfy the $(1+\epsilon)$ requirement. This forces most paths to be "well-behaved" and stay within narrow strips, which makes them susceptible to the disk-tube incidence limits.

Key Results

  • Optimal Sparsity: The paper proves that $s(n, \epsilon) = \Theta(n/\epsilon^{3/2})$ is the "correct" scaling for noncrossing Steiner spanners.
  • Improved Upper Bound: They reduce the edge count from $O(n/\epsilon^4)$ to $O(n/\epsilon^{3/2})$.
  • Nearly Matching Lower Bound: They establish a lower bound of $\Omega_\mu(n/\epsilon^{3/2-\mu})$, leaving only a tiny subpolynomial gap.
  • Efficient Construction: The spanner can be computed in $O(\frac{n \log n}{\epsilon^{3/2}})$ time.

Limitations and Future Work

  • The $\mu$ Gap: The lower bound is not perfectly tight; there is a small factor of $\epsilon^\mu$ (where $\mu$ is an arbitrarily small constant) due to the technicalities of the disk-tube incidence theorem used. Closing this final gap is a clear next step.
  • Lightness: While the paper optimizes the number of edges (sparsity), it doesn't focus on the total weight of the edges (lightness). Future work could investigate if $O(n/\epsilon^{3/2})$ sparsity can coexist with optimal lightness.
  • Non-Steiner Crossings: The authors suggest that their techniques could be used to bound the "crossing number" of standard greedy spanners (which don't use Steiner points), another long-standing open problem.

Summary updated

Abstract

A Euclidean noncrossing Steiner $(1+ε)$-spanner for a point set $P\subset\mathbb{R}^2$ is a planar straight-line graph that, for any two points $a, b \in P$, contains a path whose length is at most $1+ε$ times the Euclidean distance between $a$ and $b$. We construct a Euclidean noncrossing Steiner $(1+ε)$-spanner with $O(n/ε^{3/2})$ edges for any set of $n$ points in the plane. This result improves upon the previous best upper bound of $O(n/ε^{4})$ obtained nearly three decades ago. We also establish an almost matching lower bound: There exist $n$ points in the plane for which any Euclidean noncrossing Steiner $(1+ε)$-spanner has $Ω_μ(n/ε^{3/2-μ})$ edges for any $μ>0$. Our lower bound uses recent generalizations of the Szemerédi-Trotter theorem to disk-tube incidences in geometric measure theory.
BibTeX
@inproceedings{bhore2026euclidean,
  author = {Sujoy Bhore and Sándor Kisfaludi-Bak and Lazar Milenković and Csaba D. Tóth and Karol Węgrzycki and Sampson Wong},
  title = {{Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity}},
  booktitle = {SoCG},
  year = {2026},
  doi = {10.4230/lipics.socg.2026.15},
}

Loading related content...

Figure