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 language | English |
---|---|
Title of host publication | 35th International Symposium on Computational Geometry, SoCG 2019 |
Editors | Gill Barequet, Yusu Wang |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Number of pages | 15 |
ISBN (Electronic) | 9783959771047 |
DOIs | |
Publication status | Published - 1 Jun 2019 |
Event | 35th International Symposium on Computational Geometry, (SoCG2019) - Portland, United States Duration: 18 Jun 2019 → 21 Jun 2019 http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=80745©ownerid=35838 |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Volume | 129 |
Conference
Conference | 35th International Symposium on Computational Geometry, (SoCG2019) |
---|---|
Abbreviated title | SoCG2019 |
Country/Territory | United States |
City | Portland |
Period | 18/06/19 → 21/06/19 |
Internet address |
Keywords
- Geometric spanners
- Robustness
- Vertex failures