A Spanner for the Day After
We show how to construct (1+\varepsilon) spanner over a set $P$ of $n$ points in \mathbb{R}^d$ that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters \vartheta,\varepsilon \in (0,1) the computed spanner $G$ has O\bigl(\varepsilon^ c} \vartheta^ 6} n \log n \log\log n)^6 \bigr) edges, where $c= O(d) Furthermore, for any $k$ and any deleted set $B \subseteq P$ of $k$ points, the residual graph $G \setminus B$ is (1+\varepsilon) spanner for all the points of $P$ except for (1+\vartheta)k$ of them. No previous constructions, beyond the trivial clique with $O(n^2) edges, were known such that only a tiny additional fraction (i.e. \vartheta$ lose their distance preserving connectivity. Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one dimensional construction in a black box fashion.
SoCG