Abstract
We show how to construct a (1 + ε) -spanner over a set P of n points in Rd that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters ϑ, ε∈ (0 , 1) , the computed spanner G has O(ε-O(d)ϑ-6n(loglogn)6logn)edges. Furthermore, for anyk, and any deleted set B⊆ P of k points, the residual graph G\ B is a (1 + ε) -spanner for all the points of P except for (1 + ϑ) k of them. No previous constructions, beyond the trivial clique with O(n2) edges, were known with this resilience property (i.e., only a tiny additional fraction of vertices, ϑ| B| , 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.
Original language | English (US) |
---|---|
Journal | Discrete and Computational Geometry |
DOIs | |
State | Accepted/In press - 2020 |
Keywords
- Geometric spanners
- Reliable spanners
- Robust spanners
- Vertex failures
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics