A spanner for the day after

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Downloads (Pure)

Abstract

We show how to construct (1 + ε)-spanner over a set P of n points in ℝd that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters ϑ, ε ∈ (0, 1), the computed spanner G has O(ε−7d log7 ε−1 · ϑ−6n log n(log log n)6) edges. 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.

Original languageEnglish
Title of host publication35th International Symposium on Computational Geometry, SoCG 2019
EditorsGill Barequet, Yusu Wang
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages15
ISBN (Electronic)9783959771047
DOIs
Publication statusPublished - 1 Jun 2019
Event35th International Symposium on Computational Geometry, (SoCG2019) - Portland, United States
Duration: 18 Jun 201921 Jun 2019
http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=80745&copyownerid=35838

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume129

Conference

Conference35th International Symposium on Computational Geometry, (SoCG2019)
Abbreviated titleSoCG2019
CountryUnited States
CityPortland
Period18/06/1921/06/19
Internet address

Keywords

  • Geometric spanners
  • Robustness
  • Vertex failures

Cite this

Buchin, K., Har-Peled, S., & Oláh, D. (2019). A spanner for the day after. In G. Barequet, & Y. Wang (Eds.), 35th International Symposium on Computational Geometry, SoCG 2019 [19] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 129). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.19