LIPIcs.SoCG.2019.19.pdf
- Filesize: 0.79 MB
- 15 pages
Document
A Spanner for the Day After
Authors
Kevin Buchin 
,
Sariel Har-Peled ,
-
Part of:
Volume:
35th International Symposium on Computational Geometry (SoCG 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-06-11
File
Document Identifiers
Author Details
Cite AsGet BibTex
Kevin Buchin, Sariel Har-Peled, and Dániel Oláh. A Spanner for the Day After. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.19
https://doi.org/10.4230/LIPIcs.SoCG.2019.19
Abstract
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Geometric spanners
- vertex failures
- robustness
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- M. A. Abam and S. Har-Peled. New Constructions of SSPDs and their Applications. Computational Geometry: Theory and Applications, 45(5-6):200-214, 2012. URL: http://dx.doi.org/10.1016/j.comgeo.2011.12.003.
- B. Aronov, M. de Berg, O. Cheong, J. Gudmundsson, H. J. Haverkort, M. H. M. Smid, and A. Vigneron. Sparse geometric graphs with small dilation. Computational Geometry: Theory and Applications, 40(3):207-219, 2008. URL: http://dx.doi.org/10.1016/j.comgeo.2007.07.004.
- S. Arya, D. M. Mount, and M. Smid. Randomized and deterministic algorithms for geometric spanners of small diameter. In Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 703-712, 1994. URL: http://dx.doi.org/10.1109/SFCS.1994.365722.
- S. Arya, D. M. Mount, and M. Smid. Dynamic algorithms for geometric spanners of small diameter: Randomized solutions. Computational Geometry: Theory and Applications, 13(2):91-107, 1999. URL: http://dx.doi.org/10.1016/S0925-7721(99)00014-0.
- P. Bose, P. Carmi, V. Dujmovic, and P. Morin. Near-Optimal O(k)-Robust Geometric Spanners. CoRR, abs/1812.09913, 2018. URL: http://arxiv.org/abs/1812.09913.
- P. Bose, P. Carmi, M. Farshi, A. Maheshwari, and M. Smid. Computing the Greedy Spanner in Near-Quadratic Time. Algorithmica, 58(3):711-729, November 2010. URL: http://dx.doi.org/10.1007/s00453-009-9293-4.
- P. Bose, V. Dujmović, P. Morin, and M. Smid. Robust Geometric Spanners. SIAM Journal on Computing, 42(4):1720-1736, 2013. URL: http://dx.doi.org/10.1137/120874473.
- K. Buchin, S. Har-Peled, and D. Oláh. A Spanner for the Day After. CoRR, abs/1811.06898, 2018. URL: http://arxiv.org/abs/1811.06898.
- P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the Association for Computing Machinery, 42(1):67-90, 1995. URL: http://dx.doi.org/10.1145/200836.200853.
- P. Carmi and L. Chaitman. Stable Roommates and Geometric Spanners. In Proc. 22nd Canad. Conf. Comput. Geom.\CNFCCCG, pages 31-34, 2010. URL: http://cccg.ca/proceedings/2010/paper11.pdf.
- T. M. Chan, S. Har-Peled, and M. Jones. On Locality-Sensitive Orderings and their Applications. CoRR, abs/1809.11147, 2018. URL: http://arxiv.org/abs/1809.11147.
- J. Gudmundsson, C. Levcopoulos, and G. Narasimhan. Fast Greedy Algorithms for Constructing Sparse Geometric Spanners. SIAM J. Comput., 31(5):1479-1500, May 2002. URL: http://dx.doi.org/10.1137/S0097539700382947.
- C. Levcopoulos, G. Narasimhan, and M. Smid. Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners. In Proc. 30th Annu. ACM Sympos. Theory Comput. (STOC), pages 186-195. ACM, 1998. URL: http://dx.doi.org/10.1145/276698.276734.
- C. Levcopoulos, G. Narasimhan, and M. Smid. Improved Algorithms for Constructing Fault-Tolerant Spanners. Algorithmica, 32(1):144-156, 2002. URL: http://dx.doi.org/10.1007/s00453-001-0075-x.
- T. Lukovszki. New Results of Fault Tolerant Geometric Spanners. In Proc. 6th Workshop Algorithms Data Struct.\CNFWADS, volume 1663 of LNCS, pages 193-204. Springer, 1999. URL: http://dx.doi.org/10.1007/3-540-48447-7_20.
-
R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1995.
-
G. Narasimhan and M. Smid. Geometric spanner networks. Cambridge University Press, New York, NY, USA, 2007.
- M. Smid. Geometric Spanners with Few Edges and Degree Five. In Proc. 12th Australasian Theo. Sym. (CATS), volume 51 of CRPIT, pages 7-9, 2006. URL: http://crpit.com/abstracts/CRPITV51Smid.html.