{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:56:01Z","timestamp":1787320561298,"version":"build-2736575974"},"reference-count":67,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1042\/22"],"award-info":[{"award-number":["1042\/22"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2212129"],"award-info":[{"award-number":["CCF-2212129"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1800734"],"award-info":[{"award-number":["DMS-1800734"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2154347"],"award-info":[{"award-number":["DMS-2154347"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Given a metric space [Formula: see text], a weighted graph [Formula: see text] over [Formula: see text] is a metric [Formula: see text]-spanner of [Formula: see text] if for every [Formula: see text], [Formula: see text], where [Formula: see text] is the shortest path metric in [Formula: see text]. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points [Formula: see text], where the points are presented one at a time (i.e., after [Formula: see text] steps, we see [Formula: see text]). The algorithm is allowed to add edges to the spanner when a new point arrives; however, it is not allowed to remove any edge from the spanner. The goal is to maintain a [Formula: see text]-spanner [Formula: see text] for [Formula: see text] for all [Formula: see text], while minimizing the number of edges, and their total weight. We construct online [Formula: see text]-spanners in the Euclidean [Formula: see text]-space, [Formula: see text]-spanners for general metrics, and [Formula: see text]-spanners for ultrametrics. Most notably, in the Euclidean plane, we construct a [Formula: see text]-spanner with competitive ratio [Formula: see text], bypassing the classic lower bound [Formula: see text] for lightness, which compares the weight of the spanner to that of the minimum spanning tree.<\/jats:p>","DOI":"10.1137\/22m1534572","type":"journal-article","created":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T07:37:31Z","timestamp":1710229051000},"page":"1030-1056","source":"Crossref","is-referenced-by-count":2,"title":["Online Spanners in Metric Spaces"],"prefix":"10.1137","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0104-1659","authenticated-orcid":true,"given":"Sujoy","family":"Bhore","sequence":"first","affiliation":[{"name":"Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9578-9304","authenticated-orcid":true,"given":"Arnold","family":"Filtser","sequence":"additional","affiliation":[{"name":"Bar Ilan University, Ramat Gan, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3850-6739","authenticated-orcid":true,"given":"Hadi","family":"Khodabandeh","sequence":"additional","affiliation":[{"name":"University of California, Irvine, CA 92697 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8769-3190","authenticated-orcid":true,"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[{"name":"California State University Northridge, Los Angeles, CA 91330 USA, and Tufts University, Medford, MA 02155 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,3,12]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573969"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198522"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.021"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.01.021"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.11.001"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"P. Berman  and \nC. Coulston  , On-line algorithms for Steiner tree problems, in Proceedings of the 29th ACM Symposium on Theory of Computing (STOC), 1997, pp. 344\u2013353, https:\/\/doi.org\/10.1145\/258533.258618.","DOI":"10.1145\/258533.258618"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"M. de Berg , \nO. Cheong , \nM. J. van Kreveld , and \nM. H. Overmars  , Computational Geometry: Algorithms and Applications, 3rd ed. Springer, New York, 2008, https:\/\/www.worldcat.org\/oclc\/227584184.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.12.017"},{"key":"ref10","unstructured":"G. Bodwin , \nM. Dinitz , and \nY. Nazari  , Vertex fault-tolerant emulators, in Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), LIPIcs Leibniz Int. Proc. Inform. 215,  \nM. Braverman  , ed. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2022, pp. 25:1\u201325:22, https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2022.25."},{"key":"ref11","unstructured":"A. Borodin  and \nR. El-Yaniv  , Online Computation and Competitive Analysis, Cambridge University Press, Cambridge, UK, 1998."},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"A. Bernstein , \nS. Forster , and \nM. Henzinger  , A deamortization approach for dynamic spanner and dynamic maximal matching, in Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019, pp. 1899\u20131918, https:\/\/doi.org\/10.1137\/1.9781611975482.115.","DOI":"10.1137\/1.9781611975482.115"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/19M1286955"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.01.003"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"T. Bergamaschi , \nM. Henzinger , \nM. P. Gutenberg , \nV. V. Williams , and \nN. Wein  , New techniques and fine-grained hardness for dynamic near-additive spanners, in Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021, pp. 1836\u20131855, https:\/\/doi.org\/10.1137\/1.9781611976465.110.","DOI":"10.1137\/1.9781611976465.110"},{"key":"ref16","unstructured":"G. Bodwin  and \nS. Krinninger  , Fully dynamic spanners with worst-case update time, in the Proceedings of 24th European Symposium on Algorithms (ESA), LIPIcs Leibniz Int. Proc. Inform. 57, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2016, pp. 17:1\u201317:18, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.17."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344425"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1100-z"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"G. Borradaile , \nH. Le , and \nC. Wulff-Nilsen  , Greedy spanners are optimal in doubling metrics, in Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019, pp. 2371\u20132379, https:\/\/doi.org\/10.1137\/1.9781611975482.145.","DOI":"10.1137\/1.9781611975482.145"},{"key":"ref20","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s B.","year":"1978"},{"key":"ref21","unstructured":"S. Bhore  and \nC. D. T\u00f3th  , Online Euclidean spanners, in Proceedings of the 29th European Symposium on Algorithms (ESA), LIPIcs Leibniz Int. Proc. Inform. 204, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2021, pp. 116:1\u201316:19, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.16."},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/22M1502707"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90044-5"},{"key":"ref24","unstructured":"P. B. Callahan  and \nS. R. Kosaraju  , Faster algorithms for some geometric graph problems in higher dimensions, in Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1993, pp. 291\u2013300, http:\/\/dl.acm.org\/citation.cfm?id=313559.313777."},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson  , Approximation algorithms for shortest path motion planning, in Proceedings of the 19th ACM Symposium on Theory of Computing (STOC), 1987, pp. 56\u201365, https:\/\/doi.org\/10.1145\/28395.28402.","DOI":"10.1145\/28395.28402"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1145\/3199607"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"T.H. H. Chan , \nD. Xia , \nG. Konjevod , and \nA. Richa  , A tight lower bound for the Steiner point removal problem on trees, in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and International Workshop on Randomization and Computation Techniques in Computer Science, Springer-Verlag, Berlin, 2006, pp. 70\u201381, https:\/\/doi.org\/10.1007\/11830924_9.","DOI":"10.1007\/11830924_9"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056478"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921666"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.4064\/cm-13-2-251-254"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/2836167"},{"key":"ref32","unstructured":"J. Fischer  and \nS. Har-Peled  , Dynamic well-separated pair decomposition made easy, in Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG), 2005, pp. 235\u2013238, http:\/\/www.cccg.ca\/proceedings\/2005\/32.pdf."},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1137\/18M1184400"},{"key":"ref34","series-title":"LIPIcs Leibniz Int. Proc. Inform. 168","first-page":"47:1","volume-title":"47th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Filtser A.","year":"2020"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"A. Filtser , \nM. Kapralov , and \nN. Nouri  , Graph spanners by sketching in dynamic streams and the simultaneous communication model, in Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021, pp. 1894\u20131913, https:\/\/doi.org\/10.1137\/1.9781611976465.113.","DOI":"10.1137\/1.9781611976465.113"},{"key":"ref37","series-title":"OASIcs 69","first-page":"10:1","volume-title":"2nd Symposium on Simplicity in Algorithms (SOSA)","author":"Filtser A.","year":"2019"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1137\/18M1210678"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.10.001"},{"key":"ref40","volume-title":"Handbook of Approximation Algorithms and Metaheuri stics, Vol. 2","author":"Gudmundsson J.","year":"2018","edition":"2"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2713820"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328921"},{"key":"ref43","series-title":"LIPIcs Leibniz Int. Proc. Inform. 207","first-page":"5:1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM)","author":"Grigorescu E.","year":"2021"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_40"},{"key":"ref45","doi-asserted-by":"crossref","unstructured":"R. R. Anupam Gupta , \nK. Talwar , and \nS. W. Umboh  , LAST but not least: Online spanners for buy-at-bulk, in Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA),  \nP. N. Klein   ed. SIAM, Philadelphia, 2017, pp. 589\u2013599, https:\/\/doi.org\/10.1137\/1.9781611974782.38.","DOI":"10.1137\/1.9781611974782.38"},{"key":"ref46","unstructured":"A. Gupta  , Steiner points in tree metrics don\u2019t (really) help, in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2001, pp. 220\u2013227, https:\/\/dl.acm.org\/doi\/10.5555\/365411.365448."},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/173"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1137\/14098692X"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"ref50","doi-asserted-by":"crossref","unstructured":"M. Herlihy , \nS. Tirthapura , and \nR. Wattenhofer  , Competitive concurrent distributed queuing, in Proceedings of the 20th ACM Symposium on Principles of Distributed Computing (PODC), 2001, pp. 127\u2013133, https:\/\/doi.org\/10.1145\/383962.384001.","DOI":"10.1145\/383962.384001"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"ref52","doi-asserted-by":"crossref","unstructured":"J. M. Keil  , Approximating the complete Euclidean graph, in Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (SWAT), Lecture Notes in Comput. Sci. 318, Springer, New York, 1988, pp. 208\u2013213, https:\/\/doi.org\/10.1007\/3-540-19487-8_23.","DOI":"10.1007\/3-540-19487-8_23"},{"key":"ref53","unstructured":"R. Krauthgamer  and \nJ. R. Lee  , Navigating nets: Simple algorithms for proximity search, in Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2004, pp. 798\u2013807, https:\/\/dl.acm.org\/doi\/10.5555\/982792.982913."},{"key":"ref54","doi-asserted-by":"crossref","unstructured":"H. Le  and \nS. Solomon  , Truly optimal Euclidean spanners, in Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS), 2019, pp. 1078\u20131100, https:\/\/doi.org\/10.1109\/FOCS.2019.00069.","DOI":"10.1109\/FOCS.2019.00069"},{"key":"ref55","unstructured":"H. Le  and \nS. Solomon  , Light Euclidean spanners with Steiner points, in Proceedings of the 28th Annual European Symposium on Algorithms (ESA), LIPIcs Leibniz Int. Proc. Inform. 173, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2020, pp. 67:1\u201367:22, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.67."},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"ref57","doi-asserted-by":"crossref","unstructured":"J. Naor , \nD. Panigrahi , and \nM. Singh  , Online node-weighted Steiner tree and related problems, in Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), 2011, pp. 210\u2013219, https:\/\/doi.org\/10.1109\/FOCS.2011.65.","DOI":"10.1109\/FOCS.2011.65"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9504-7"},{"key":"ref63","unstructured":"J. Ruppert  and \nR. Seidel  , Approximating the \\(d\\)-dimensional complete Euclidean graph, in Proceedings of the 3rd Canadian Conference on Computational Geometry (CCCG), 1991, pp. 207\u2013210."},{"key":"ref64","volume-title":"Handbook of Approximation Algorithms and Metaheuristics, Vol. 2","author":"Smid M. H. M.","year":"2018","edition":"2"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.02.001"},{"key":"ref66","unstructured":"S. W. Umboh  , private communication, 2021."},{"key":"ref67","doi-asserted-by":"crossref","unstructured":"A. C.C. Yao  , Space-time tradeoff for answering range queries (extended abstract), in Proceedings of the 14th ACM Symposium on Theory of Computing (STOC), 1982, pp. 128\u2013136, https:\/\/doi.org\/10.1145\/800070.802185.","DOI":"10.1145\/800070.802185"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1534572","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:57:50Z","timestamp":1787317070000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1534572"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":67,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/22M1534572"],"URL":"https:\/\/doi.org\/10.1137\/22m1534572","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}