Near-Optimal $O(k)$-Robust Geometric Spanners

For any constants $dge 1$, $epsilon >0$, $t>1$, and any $n$-point set $Psubsetmathbb{R}^d$, we show that there is a geometric graph $G=(P,E)$ having $O(nlog^2 nloglog n)$ edges with the following property: For any $Fsubseteq P$, there exists $F^+supseteq F$, $|F^+| le (1+epsilon)|F|$ such that, for any pair $p,qin Psetminus F^+$, the graph $G-F$ contains a path from $p$ to $q$ whose (Euclidean) length is at most $t$ times the Euclidean distance between $p$ and $q$. In the terminology of robust spanners (Bose et al, SICOMP, 42(4):1720--1736, 2013) the graph $G$ is a $(1+epsilon)k$-robust $t$-spanner of $P$. This construction is sparser than the recent constructions of Buchin, Ol`ah, and Har-Peled (arXiv:1811.06898) who prove the existence of $(1+epsilon)k$-robust $t$-spanners with $nlog^{O(d)} n$ edges.