TY - JOUR
T1 - A Spanner for the Day After
AU - Buchin, Kevin
AU - Har-Peled, Sariel
AU - Oláh, Dániel
N1 - Funding Information:
A preliminary version of the paper appeared in SoCG 2019 []. Sariel Har-Peled was partially supported by NSF AF awards CCF-1421231 and CCF-1907400. Dániel Oláh was supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.
Publisher Copyright:
© 2020, The Author(s).
PY - 2020/12
Y1 - 2020/12
N2 - 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.
AB - 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.
KW - Geometric spanners
KW - Reliable spanners
KW - Robust spanners
KW - Vertex failures
UR - http://www.scopus.com/inward/record.url?scp=85089101590&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089101590&partnerID=8YFLogxK
U2 - 10.1007/s00454-020-00228-6
DO - 10.1007/s00454-020-00228-6
M3 - Article
AN - SCOPUS:85089101590
SN - 0179-5376
VL - 64
SP - 1167
EP - 1191
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 4
ER -