A Spanner for the Day After

Kevin Buchin, Sariel Har-Peled, Dániel Oláh

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)1167-1191
Number of pages25
JournalDiscrete and Computational Geometry
Volume64
Issue number4
DOIs
StatePublished - Dec 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

Fingerprint

Dive into the research topics of 'A Spanner for the Day After'. Together they form a unique fingerprint.

Cite this