Online Euclidean Spanners

Abstract

In this paper, we study the online Euclidean spanners problem for points in ${\mathbb{R}}^d$. Suppose we are given a sequence of $n$ points $(s_1,s_2,\dots ,s_n)$ in ${\mathbb{R}}^d$, where point $s_i$ is presented in step~$i$ for $i=1,\dots ,n$. The objective of an online algorithm is to maintain a geometric $t$-spanner on $S_i=\{s_1,\dots ,s_i\}$ for each step~$i$. First, we establish a lower bound of $\Omega ({\epsilon }^{-1}\log n/\log {\epsilon }^{-1})$ for the competitive ratio of any online $(1+\epsilon )$-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+\epsilon )$-spanner with competitive ratio $O({\epsilon }^{-1}\log n/\log {\epsilon }^{-1})$. Next, we design online algorithms for sequences of points in ${\mathbb{R}}^d$, for any constant $d\ge 2$, under the $L_2$ norm. We show that previously known incremental algorithms achieve a competitive ratio $O({\epsilon }^{-(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 $\epsilon$. We describe an online Steiner $(1+\epsilon )$-spanner algorithm with competitive ratio $O({\epsilon }^{(1-d)/2}\log n)$. As a counterpart, we show that the dependence on $n$ cannot be eliminated in dimensions $d\ge 2$. In particular, we prove that any online spanner algorithm for a sequence of $n$ points in ${\mathbb{R}}^d$ under the $L_2$ norm has competitive ratio $\Omega (f(n))$, where ${\lim }_{n\to \infty }f(n)=\infty$. Finally, we provide improved lower bounds under the $L_1$ norm: $\Omega ({\epsilon }^{-2}/\log {\epsilon }^{-1})$ in the plane and $\Omega ({\epsilon }^{-d})$ in ${\mathbb{R}}^d$ for $d\ge 3$.

22 pages, 8 figures. An extended abstract of this paper will appear in the Proceedings of ESA 2021