Home Bookmarks Papers Blog

A Spanner for the Day After $\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\Of}{{\mathcal{O}}}% \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\epsR}{\vartheta}% \newcommand{\pts}{s}$


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.
Last modified: Tue 2019-04-09 17:00:09 UTC 2019 by Sariel Har-Peled