Online Euclidean Spanners

Sujoy Bhore, Csaba D. Tóth

Introduction: The Online Spanner Problem

This research addresses the challenge of maintaining a $(1+\epsilon)$-spanner—a graph that approximates all-pairs Euclidean distances—as points arrive one-by-one. In this online setting, edges can be added as new points appear, but they can never be removed. The objective is to minimize the competitive ratio: the total weight of the online network compared to the weight of an optimal network built with full knowledge of all points in advance.

Maintaining efficiency is difficult because the "optimal" target is non-monotonic; adding a new point might allow for a much more efficient global structure in hindsight, but the online algorithm is bound by its previous, potentially suboptimal, decisions.

The Power of Steiner Points

A major contribution of this work is the use of Steiner points—extra vertices added to the graph that are not part of the original input set. In an online setting, Steiner points allow for "bundling." Without them, every new connection might require a long, expensive edge. With them, the algorithm can build a shared infrastructure that many future points can utilize.

Comparison between a standard spanner (a) and a Steiner spanner (b). The red Steiner point in (b) allows for a more efficient connection of the three black input points.

Algorithmic Strategies

The authors employ several sophisticated geometric techniques to manage network growth:

  • Hierarchical Clustering (1D): For points on a line, a bucketing strategy based on edge weights is used. By carefully deciding when a new point is "close enough" to an existing cluster, the algorithm maintains a tight competitive ratio.
  • The Backbone Strategy: For higher dimensions ($d \ge 2$), a two-stage Steiner algorithm groups potential edges into "buckets" based on direction and weight. When a bucket's first edge appears, the algorithm builds a "backbone" using grids and shallow-light trees. Subsequent edges in that bucket simply "plug into" this backbone with minimal additional weight.
  • Directional Bucketing: By partitioning the space into narrow cones, the algorithm approximates Euclidean distances using structures that are essentially one-dimensional, simplifying the weight analysis.

Key Results and Lower Bounds

The study establishes several critical bounds for the competitive ratio:

  • 1D Case: Settled with a tight competitive ratio of $\Theta(\epsilon^{-1} \log n / \log \epsilon^{-1})$.
  • Higher Dimensions (No Steiner): Existing incremental algorithms achieve $O(\epsilon^{-(d+1)} \log n)$.
  • Higher Dimensions (With Steiner): Steiner points improve the ratio to $O(\epsilon^{(1-d)/2} \log n)$. For $d=2$, this is $O(\epsilon^{-1/2} \log n)$, a significant improvement.

To prove these limits, the authors use adversarial constructions, strategically placing points to force any online algorithm to perform poorly. They demonstrate that in dimensions $d \ge 2$, the competitive ratio must depend on $n$ (the number of points) and cannot be a constant.

Adversarial construction used to analyze the competitive ratio. The arcs represent potential paths between points as they are revealed sequentially.

Limitations and Future Work

While this work settles the 1D case, gaps remain for higher dimensions. Future research may explore whether the $\log n$ factor can be further reduced or if the dependence on $\epsilon$ is strictly necessary for Steiner spanners. Additionally, the authors suggest investigating "online algorithms with recourse," where a limited number of edge deletions are permitted to maintain network efficiency over time.

Summary updated

Abstract

In this paper, we study the online Euclidean spanners problem for points in ℝ^d. Given a set S of n points in ℝ^d, a t-spanner on S is a subgraph of the underlying complete graph G = (S,binom(S,2)), that preserves the pairwise Euclidean distances between points in S to within a factor of t, that is the stretch factor. Suppose we are given a sequence of n points (s₁,s₂,…, s_n) in ℝ^d, where point s_i is presented in step i for i = 1,…, n. The objective of an online algorithm is to maintain a geometric t-spanner on S_i = {s₁,…, s_i} for each step i. The algorithm is allowed to add new edges to the spanner when a new point is presented, but cannot remove any edge from the spanner. The performance of an online algorithm is measured by its competitive ratio, which is the supremum, over all sequences of points, of the ratio between the weight of the spanner constructed by the algorithm and the weight of an optimum spanner. Here the weight of a spanner is the sum of all edge weights. First, we establish a lower bound of Ω(ε^{-1}log n / log ε^{-1}) for the competitive ratio of any online (1+ε)-spanner algorithm, for a sequence of n points in 1-dimension. We show that this bound is tight, and there is an online algorithm that can maintain a (1+ε)-spanner with competitive ratio O(ε^{-1}log n / log ε^{-1}). Next, we design online algorithms for sequences of points in ℝ^d, for any constant d ≥ 2, under the L₂ norm. We show that previously known incremental algorithms achieve a competitive ratio O(ε^{-(d+1)}log n). However, if the algorithm is allowed to use additional points (Steiner points), then it is possible to substantially improve the competitive ratio in terms of ε. We describe an online Steiner (1+ε)-spanner algorithm with competitive ratio O(ε^{(1-d)/2} log n). As a counterpart, we show that the dependence on n cannot be eliminated in dimensions d ≥ 2. In particular, we prove that any online spanner algorithm for a sequence of n points in ℝ^d under the L₂ norm has competitive ratio Ω(f(n)), where lim_{n → ∞}f(n) = ∞. Finally, we provide improved lower bounds under the L₁ norm: Ω(ε^{-2}/log ε^{-1}) in the plane and Ω(ε^{-d}) in ℝ^d for d ≥ 3.
BibTeX
@article{bhore2025online,
  author = {Sujoy Bhore and Csaba D. Tóth},
  title = {{Online Euclidean Spanners}},
  journal = {ACM Trans. Algorithms},
  year = {2025},
  url = {https://openreview.net/forum?id=hILZrmfZst},
}
Figure