Document Open Access Logo

A Spanner for the Day After

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2019.19.pdf
  • Filesize: 0.79 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Geometric spanners
  • vertex failures
  • robustness

Metrics

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.

Cite As Get 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

Author Details

Kevin Buchin
  • Department of Mathematics and Computing Science, TU Eindhoven, The Netherlands
Sariel Har-Peled
  • Department of Computer Science, University of Illinois at Urbana-Champaign, USA
Dániel Oláh
  • Department of Mathematics and Computing Science, TU Eindhoven, The Netherlands

Funding

  • Har-Peled, Sariel: Work on this paper was partially supported by a NSF AF awards CCF-1421231.
  • Oláh, Dániel: Supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1995. Google Scholar
  17. G. Narasimhan and M. Smid. Geometric spanner networks. Cambridge University Press, New York, NY, USA, 2007. Google Scholar
  18. 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.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact