2026-08-06T04:40:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10423 2024-03-06T10:45:57Z ddc:004 open_access

A Spanner for the Day After Buchin, Kevin Har-Peled, Sariel Oláh, Dániel Geometric spanners vertex failures robustness We show how to construct (1+epsilon)-spanner over a set P of n points in R^d that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters theta, epsilon in (0,1), the computed spanner G has O(epsilon^{-7d} log^7 epsilon^{-1} * theta^{-6} n log n (log log n)^6) edges. Furthermore, for any k, and any deleted set B subseteq P of k points, the residual graph G \ B is (1+epsilon)-spanner for all the points of P except for (1+theta)k of them. No previous constructions, beyond the trivial clique with O(n^2) edges, were known such that only a tiny additional fraction (i.e., theta) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kevin Buchin and Sariel Har-Peled and Dániel Oláh 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.19 urn:nbn:de:0030-drops-104237 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.19 eng https://creativecommons.org/licenses/by/3.0/legalcode