A spanner for the day after

Kevin A. Buchin, Sariel Har-Peled, Dániel Olah

Onderzoeksoutput: Andere bijdrageOverige bijdrageAcademic

11 Downloads (Pure)


We show how to construct (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(ε−cϑ−6nlogn(loglogn)6) edges, where c=O(d). Furthermore, for any k, and any deleted set B⊆P of k points, the residual graph G∖B is (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 such that only a tiny additional fraction (i.e., ϑ) 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.
Originele taal-2Engels
UitgeverCornell University
Aantal pagina's21
StatusGepubliceerd - 2018


Duik in de onderzoeksthema's van 'A spanner for the day after'. Samen vormen ze een unieke vingerafdruk.

Citeer dit