Home Bookmarks Papers Blog


Kevin Buchin, Sariel Har-Peled, and Dániel Oláh.
We show how to construct $(1+\eps)$-spanner over a set $P$ of $n$ points in $\Re^d$ that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters $\epsR,\eps \in (0,1)$, the computed spanner $G$ has $\Of \bigl(\eps^{-c} \epsR^{-6} n \log n (\log\log n)^6 \bigr)$ edges, where $c= \Of(d)$. Furthermore, for any $k$, and any deleted set $B \subseteq P$ of $k$ points, the residual graph $G \setminus B$ is $(1+\eps)$-spanner for all the points of $P$ except for $(1+\epsR)k$ of them. No previous constructions, beyond the trivial clique with $\Of(n^2)$ edges, were known such that only a tiny additional fraction (i.e., $\epsR$) 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.
PDF.
Slides from SoCG talk (given by Dániel).