{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:19:12Z","timestamp":1759335552722,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T00:00:00Z","timestamp":1596672000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T00:00:00Z","timestamp":1596672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["NETWORKS-024.002.003"],"award-info":[{"award-number":["NETWORKS-024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1421231"],"award-info":[{"award-number":["CCF-1421231"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,12]]},"abstract":"Abstract<\/jats:title>We show how to construct a $$(1+\\varepsilon )$$<\/jats:tex-math>\n\n(<\/mml:mo>\n1<\/mml:mn>\n+<\/mml:mo>\n\u03b5<\/mml:mi>\n)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>-spanner over a set $${P}$$<\/jats:tex-math>\nP<\/mml:mi>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> of n<\/jats:italic> points in $${\\mathbb {R}}^d$$<\/jats:tex-math>\n\n\nR<\/mml:mi>\n<\/mml:mrow>\nd<\/mml:mi>\n<\/mml:msup>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters $${\\vartheta },\\varepsilon \\in (0,1)$$<\/jats:tex-math>\n\n\u03d1<\/mml:mi>\n,<\/mml:mo>\n\u03b5<\/mml:mi>\n\u2208<\/mml:mo>\n(<\/mml:mo>\n0<\/mml:mn>\n,<\/mml:mo>\n1<\/mml:mn>\n)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the computed spanner $${G}$$<\/jats:tex-math>\nG<\/mml:mi>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> has $$\\begin{aligned} {{\\mathcal {O}}}\\bigl (\\varepsilon ^{-O(d)} {\\vartheta }^{-6} n(\\log \\log n)^6 \\log n \\bigr ) \\end{aligned}$$<\/jats:tex-math>\n\n\n\n\n\nO<\/mml:mi>\n\n(<\/mml:mo>\n<\/mml:mrow>\n\n\u03b5<\/mml:mi>\n\n-<\/mml:mo>\nO<\/mml:mi>\n(<\/mml:mo>\nd<\/mml:mi>\n)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:msup>\n\n\n\u03d1<\/mml:mi>\n<\/mml:mrow>\n\n-<\/mml:mo>\n6<\/mml:mn>\n<\/mml:mrow>\n<\/mml:msup>\nn<\/mml:mi>\n\n\n(<\/mml:mo>\nlog<\/mml:mo>\nlog<\/mml:mo>\nn<\/mml:mi>\n)<\/mml:mo>\n<\/mml:mrow>\n6<\/mml:mn>\n<\/mml:msup>\nlog<\/mml:mo>\nn<\/mml:mi>\n\n)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:mrow>\n<\/mml:mtd>\n<\/mml:mtr>\n<\/mml:mtable>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:disp-formula>edges. Furthermore, for any<\/jats:italic>k<\/jats:italic>, and any<\/jats:italic> deleted set $${{B}}\\subseteq {P}$$<\/jats:tex-math>\n\nB<\/mml:mi>\n\u2286<\/mml:mo>\nP<\/mml:mi>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> of k<\/jats:italic> points, the residual graph $${G}\\setminus {{B}}$$<\/jats:tex-math>\n\nG<\/mml:mi>\n\\<\/mml:mo>\nB<\/mml:mi>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a $$(1+\\varepsilon )$$<\/jats:tex-math>\n\n(<\/mml:mo>\n1<\/mml:mn>\n+<\/mml:mo>\n\u03b5<\/mml:mi>\n)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>-spanner for all the points of $${P}$$<\/jats:tex-math>\nP<\/mml:mi>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> except for $$(1+{\\vartheta })k$$<\/jats:tex-math>\n\n(<\/mml:mo>\n1<\/mml:mn>\n+<\/mml:mo>\n\u03d1<\/mml:mi>\n)<\/mml:mo>\nk<\/mml:mi>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> of them. No previous constructions, beyond the trivial clique with $${{\\mathcal {O}}}(n^2)$$<\/jats:tex-math>\n\nO<\/mml:mi>\n(<\/mml:mo>\n\nn<\/mml:mi>\n2<\/mml:mn>\n<\/mml:msup>\n)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> edges, were known with this resilience property (i.e., only a tiny additional fraction of vertices, $$\\vartheta |B|$$<\/jats:tex-math>\n\n\u03d1<\/mml:mi>\n|<\/mml:mo>\nB<\/mml:mi>\n|<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>, 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.<\/jats:p>","DOI":"10.1007\/s00454-020-00228-6","type":"journal-article","created":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T19:02:45Z","timestamp":1596740565000},"page":"1167-1191","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Spanner for the Day After"],"prefix":"10.1007","volume":"64","author":[{"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[]},{"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7179-3552","authenticated-orcid":false,"given":"D\u00e1niel","family":"Ol\u00e1h","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,6]]},"reference":[{"issue":"4","key":"228_CR1","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/s00454-009-9137-7","volume":"41","author":"MA Abam","year":"2009","unstructured":"Abam, M.A., de Berg, M., Farshi, M., Gudmundsson, J.: Region-fault tolerant geometric spanners. Discrete Comput. Geom. 41(4), 556\u2013582 (2009)","journal-title":"Discrete Comput. Geom."},{"issue":"5\u20136","key":"228_CR2","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.comgeo.2011.12.003","volume":"45","author":"MA Abam","year":"2012","unstructured":"Abam, M.A., Har-Peled, S.: New constructions of SSPDs and their applications. Comput. Geom. 45(5\u20136), 200\u2013214 (2012)","journal-title":"Comput. Geom."},{"issue":"3","key":"228_CR3","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1017\/S0963548307008851","volume":"17","author":"N Alon","year":"2008","unstructured":"Alon, N., Schwartz, O., Shapira, A.: An elementary construction of constant-degree expanders. Comb. Probab. Comput. 17(3), 319\u2013327 (2008)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"228_CR4","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.comgeo.2007.07.004","volume":"40","author":"B Aronov","year":"2008","unstructured":"Aronov, B., de Berg, M., Cheong, O., Gudmundsson, J., Haverkort, H., Smid, M., Vigneron, A.: Sparse geometric graphs with small dilation. Comput. Geom. 40(3), 207\u2013219 (2008)","journal-title":"Comput. Geom."},{"key":"228_CR5","unstructured":"Arya, S., Mount, D.M., Smid, M.: Randomized and deterministic algorithms for geometric spanners of small diameter. In: 35th Annual Symposium on Foundations of Computer Science (Santa Fe 1994), pp. 703\u2013712. IEEE, Los Alamitos (1994)"},{"issue":"2","key":"228_CR6","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0925-7721(99)00014-0","volume":"13","author":"S Arya","year":"1999","unstructured":"Arya, S., Mount, D.M., Smid, M.: Dynamic algorithms for geometric spanners of small diameter: randomized solutions. Comput. Geom. 13(2), 91\u2013107 (1999)","journal-title":"Comput. Geom."},{"key":"228_CR7","unstructured":"Bose, P., Carmi, P., Dujmovi\u0107, V., Morin, P.: Near-optimal $$O(k)$$-robust geometric spanners (2018). arXiv:1812.09913"},{"issue":"3","key":"228_CR8","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1007\/s00453-009-9293-4","volume":"58","author":"P Bose","year":"2010","unstructured":"Bose, P., Carmi, P., Farshi, M., Maheshwari, A., Smid, M.: Computing the greedy spanner in near-quadratic time. Algorithmica 58(3), 711\u2013729 (2010)","journal-title":"Algorithmica"},{"issue":"4","key":"228_CR9","doi-asserted-by":"publisher","first-page":"1720","DOI":"10.1137\/120874473","volume":"42","author":"P Bose","year":"2013","unstructured":"Bose, P., Dujmovi\u0107, V., Morin, P., Smid, M.: Robust geometric spanners. SIAM J. Comput. 42(4), 1720\u20131736 (2013)","journal-title":"SIAM J. Comput."},{"key":"228_CR10","unstructured":"Buchin, K., Har-Peled, S., Ol\u00e1h, D.: A spanner for the day after. In: 35th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 129, #\u00a019. Leibniz-Zent. Inform., Wadern (2019)"},{"key":"228_CR11","unstructured":"Buchin, K., Hulshof, T., Ol\u00e1h, D.: $${\\cal{O}}(k)$$-robust spanners in one dimension (2018). arXiv:1803.08719"},{"issue":"1","key":"228_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"PB Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to $$k$$-nearest-neighbors and $$n$$-body potential fields. J. ACM 42(1), 67\u201390 (1995)","journal-title":"J. ACM"},{"key":"228_CR13","unstructured":"Carmi, P., Chaitman, L.: Stable roommates and geometric spanners. In: Canadian Conference on Computational Geometry (Winnipeg 2010), pp. 31\u201334 (2010)"},{"key":"228_CR14","unstructured":"Chan, T.M., Har-Peled, S., Jones, M.: On locality-sensitive orderings and their applications. In: 10th Innovations in Theoretical Computer Science. Leibniz Int. Proc. Inform., vol. 124, #\u00a021. Leibniz-Zent. Inform., Wadern (2019)"},{"issue":"3","key":"228_CR15","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O Gabber","year":"1981","unstructured":"Gabber, O., Galil, Z.: Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci. 22(3), 407\u2013420 (1981)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"228_CR16","doi-asserted-by":"publisher","first-page":"1479","DOI":"10.1137\/S0097539700382947","volume":"31","author":"J Gudmundsson","year":"2002","unstructured":"Gudmundsson, J., Levcopoulos, Ch., Narasimhan, G.: Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31(5), 1479\u20131500 (2002)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"228_CR17","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439\u2013561 (2006)","journal-title":"Bull. Am. Math. Soc."},{"key":"228_CR18","doi-asserted-by":"crossref","unstructured":"Levcopoulos, Ch., Narasimhan, G., Smid, M.: Efficient algorithms for constructing fault-tolerant geometric spanners. In: 30th Annual ACM Symposium on Theory of Computing (Dallas 1998), pp. 186\u2013195. ACM, New York (1999)","DOI":"10.1145\/276698.276734"},{"issue":"1","key":"228_CR19","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s00453-001-0075-x","volume":"32","author":"Ch Levcopoulos","year":"2002","unstructured":"Levcopoulos, Ch., Narasimhan, G., Smid, M.: Improved algorithms for constructing fault-tolerant spanners. Algorithmica 32(1), 144\u2013156 (2002)","journal-title":"Algorithmica"},{"key":"228_CR20","doi-asserted-by":"crossref","unstructured":"Lukovszki, T.: New results of fault tolerant geometric spanners. In: Workshop on Algorithms and Data Structures (Vancouver 1999). Lecture Notes in Computer Science, vol. 1663, pp. 193\u2013204. Springer, Berlin (1999)","DOI":"10.1007\/3-540-48447-7_20"},{"key":"228_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"228_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)"},{"issue":"1","key":"228_CR23","doi-asserted-by":"publisher","first-page":"157","DOI":"10.2307\/3062153","volume":"155","author":"O Reingold","year":"2002","unstructured":"Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig\u2013zag graph product, and new constant-degree expanders. Ann. Math. 155(1), 157\u2013187 (2002)","journal-title":"Ann. Math."},{"key":"228_CR24","unstructured":"Smid, M.H.M.: Geometric spanners with few edges and degree five. In: Theory of Computing 2006 (Hobart), pp. 7\u20139. Australian Computer Society, Darlinghurst (2006)"},{"key":"228_CR25","doi-asserted-by":"crossref","unstructured":"Willard, D.E.: Maintaining dense sequential files in a dynamic environment (extended abstract). In: 14th Annual ACM Symposium on Theory of Computing (San Francisco 1982), pp. 114\u2013121. ACM, New York (1982)","DOI":"10.1145\/800070.802183"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00228-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00228-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00228-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T23:52:02Z","timestamp":1628207522000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00228-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,6]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["228"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00228-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2020,8,6]]},"assertion":[{"value":"17 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}