{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T22:20:38Z","timestamp":1780611638612,"version":"3.54.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["DMS-1800734 and DMS-2154347"],"award-info":[{"award-number":["DMS-1800734 and DMS-2154347"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"\n In this article, we study the online Euclidean spanners problem for points in\n \n \\(\\mathbb{R}^{d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Given a set\n \n \\(S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n points in\n \n \\(\\mathbb{R}^{d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , a\n \n \\(t\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -spanner on\n \n \\(S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is a subgraph of the underlying complete graph\n \n \\(G=(S,\\binom{S}{2})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , that preserves the pairwise Euclidean distances between points in\n \n \\(S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n to within a factor of\n \n \\(t\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , that is the\n stretch factor<\/jats:italic>\n . Suppose we are given a sequence of\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n points\n \n \\((s_{1},s_{2},\\ldots,s_{n})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in\n \n \\(\\mathbb{R}^{d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where point\n \n \\(s_{i}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is presented in step\n \n \\(i\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for\n \n \\(i=1,\\ldots,n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . The objective of an online algorithm is to maintain a geometric\n \n \\(t\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -spanner on\n \n \\(S_{i}=\\{s_{1},\\ldots,s_{i}\\}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for each step\n \n \\(i\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . The algorithm is allowed to\n add<\/jats:italic>\n new edges to the spanner when a new point is presented but cannot\n remove<\/jats:italic>\n any edge from the spanner. The performance of an online algorithm is measured by its competitive ratio, which is the supremum, over all sequences of points, of the ratio between the weight of the spanner constructed by the algorithm and the weight of an optimum spanner. Here, the weight of a spanner is the sum of all edge weights.\n <\/jats:p>\n \n First, we establish a lower bound of\n \n \\(\\Omega(\\varepsilon^{-1}\\log n\/\\log\\varepsilon^{-1})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for the competitive ratio of any online\n \n \\((1+\\varepsilon)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -spanner algorithm, for a sequence of\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n points in 1-dimension. We show that this bound is tight, and there is an online algorithm that can maintain a\n \n \\((1+\\varepsilon)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -spanner with competitive ratio\n \n \\(O(\\varepsilon^{-1}\\log n\/\\log\\varepsilon^{-1})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Next, we design online algorithms for sequences of points in\n \n \\(\\mathbb{R}^{d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , for any constant\n \n \\(d\\geq 2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , under the\n \n \\(L_{2}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n norm. We show that previously known incremental algorithms achieve a competitive ratio\n \n \\(O(\\varepsilon^{-(d+1)}\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . However, if the algorithm is allowed to use additional points (Steiner points), then it is possible to substantially improve the competitive ratio in terms of\n \n \\(\\varepsilon\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We describe an online Steiner\n \n \\((1+\\varepsilon)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -spanner algorithm with competitive ratio\n \n \\(O(\\varepsilon^{(1-d)\/2}\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . As a counterpart, we show that the dependence on\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n cannot be eliminated in dimensions\n \n \\(d\\geq 2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . In particular, we prove that any online spanner algorithm for a sequence of\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n points in\n \n \\(\\mathbb{R}^{d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n under the\n \n \\(L_{2}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n norm has competitive ratio\n \n \\(\\Omega(f(n))\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where\n \n \\(\\lim_{n\\rightarrow\\infty}f(n)=\\infty\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Finally, we provide improved lower bounds under the\n \n \\(L_{1}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n norm:\n \n \\(\\Omega(\\varepsilon^{-2}\/\\log\\varepsilon^{-1})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in the plane and\n \n \\(\\Omega(\\varepsilon^{-d})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in\n \n \\(\\mathbb{R}^{d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for\n \n \\(d\\geq 3\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1145\/3681790","type":"journal-article","created":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T14:01:01Z","timestamp":1723125661000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Online Euclidean Spanners"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0104-1659","authenticated-orcid":false,"given":"Sujoy","family":"Bhore","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Bombay, Mumbai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8769-3190","authenticated-orcid":false,"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[{"name":"California State University Northridge, Los Angeles, CA, USA and Tufts University, Medford, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,11,4]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198522"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573969"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365722"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523237"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.021"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93417"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344425"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.110"},{"key":"e_1_3_2_11_2","first-page":"344","volume-title":"Proceedings of the 29th ACM Symposium on Theory of Computing (STOC)","author":"Berman Piotr","year":"1997","unstructured":"Piotr Berman and Chris Coulston. 1997. On-line algorithms for Steiner tree problems. In Proceedings of the 29th ACM Symposium on Theory of Computing (STOC), 344\u2013353."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.115"},{"key":"e_1_3_2_13_2","first-page":"18:1","volume-title":"Proceedings of the 30th European Symposium on Algorithms (ESA)","volume":"244","author":"Bhore Sujoy","year":"2022","unstructured":"Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, and Csaba D. T\u00f3th. 2022. Online spanners in metric spaces. In Proceedings of the 30th European Symposium on Algorithms (ESA), LIPIcs, Vol. 244, Schloss Dagstuhl, 18:1\u201318:20."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/22M1502707"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/290169"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.01.003"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366854"},{"key":"e_1_3_2_18_2","first-page":"291","volume-title":"Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Callahan Paul B.","year":"1993","unstructured":"Paul B. Callahan and S. Rao Kosaraju. 1993. Faster algorithms for some geometric graph problems in higher dimensions. In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), 291\u2013300."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.06.010"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1246493"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/10515.10534"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90044-5"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28402"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/160985.160998"},{"key":"e_1_3_2_26_2","first-page":"215","volume-title":"Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Das Gautam","year":"1995","unstructured":"Gautam Das, Giri Narasimhan, and Jeffrey S. Salowe. 1995. A new way to weigh malnourished Euclidean graphs. In Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), 215\u2013222."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/13094791X"},{"key":"e_1_3_2_29_2","first-page":"235","volume-title":"Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG)","author":"Fischer John","year":"2005","unstructured":"John Fischer and Sariel Har-Peled. 2005. Dynamic well-separated pair decomposition made easy. In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG), 235\u2013238."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.10.001"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2713820"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_40"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/140955276"},{"key":"e_1_3_2_34_2","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"Gudmundsson Joachim","year":"2018","unstructured":"Joachim Gudmundsson and Christian Knauer. 2018. Dilation and detours in geometric networks. In Handbook of Approximation Algorithms and Metaheuristics (2nd ed.). Vol. 2. Chapman and Hall\/CRC.","edition":"2"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328921"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.66"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.5555\/2031416"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19487-8_23"},{"key":"e_1_3_2_41_2","first-page":"243","volume-title":"Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Khuller Samir","year":"1993","unstructured":"Samir Khuller, Balaji Raghavachari, and Neal E. Young. 1993. Balancing minimum spanning and shortest path trees. In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), 243\u2013250."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00069"},{"key":"e_1_3_2_43_2","first-page":"67:1","volume-title":"Proceedings of the 28th European Symposium on Algorithms (ESA)","volume":"173","author":"Le Hung","year":"2020","unstructured":"Hung Le and Shay Solomon. 2020. Light Euclidean spanners with Steiner points. In Proceedings of the 28th European Symposium on Algorithms (ESA), LIPIcs, Vol. 173, Schloss Dagstuhl, 67:1\u201367:22."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585185"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/130917703"},{"key":"e_1_3_2_46_2","volume-title":"Handbook of Discrete and Computational Geometry","author":"Mitchell Joseph S. B.","year":"2018","unstructured":"Joseph S. B. Mitchell and Wolfgang Mulzer. 2018. Proximity algorithms. In Handbook of Discrete and Computational Geometry (3rd ed.). CRC Press, Boca Raton, FL.","edition":"3"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.65"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"},{"key":"e_1_3_2_49_2","first-page":"540","volume-title":"Proceedings of the 13th ACM Symposium on Theory of Computing (STOC)","author":"Rao Satish B.","year":"1998","unstructured":"Satish B. Rao and Warren D. Smith. 1998. Approximating geometrical graphs via \u201cspanners\u201d and \u201cbanyans\u201d. In Proceedings of the 13th ACM Symposium on Theory of Computing (STOC), 540\u2013550."},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9504-7"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.02.001"},{"key":"e_1_3_2_52_2","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"Smid Michiel H. M.","year":"2018","unstructured":"Michiel H. M. Smid. 2018. The well-separated pair decomposition and its applications. In Handbook of Approximation Algorithms and Metaheuristics (2nd ed.). Vol. 2. Chapman and Hall\/CRC.","edition":"2"},{"issue":"2","key":"e_1_3_2_53_2","first-page":"113","article-title":"Euclidean Steiner shallow-light trees","volume":"6","author":"Solomon Shay","year":"2015","unstructured":"Shay Solomon. 2015. Euclidean Steiner shallow-light trees. Journal of Computational Geometry 6, 2 (2015), 113\u2013139.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211059"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3681790","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3681790","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:03Z","timestamp":1750295403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3681790"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3681790"],"URL":"https:\/\/doi.org\/10.1145\/3681790","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,4]]},"assertion":[{"value":"2021-08-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-21","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}