{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T15:40:19Z","timestamp":1772466019938,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2237288"],"award-info":[{"award-number":["2237288"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2237288"],"award-info":[{"award-number":["2237288"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101043159"],"award-info":[{"award-number":["101043159"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1991\/1"],"award-info":[{"award-number":["1991\/1"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","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":[[2026,3]]},"DOI":"10.1007\/s00454-025-00803-9","type":"journal-article","created":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T14:13:56Z","timestamp":1764598436000},"page":"625-659","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Euclidean Tree Covers"],"prefix":"10.1007","volume":"75","author":[{"given":"Hsien-Chih","family":"Chang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Conroy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hung","family":"Le","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5777-2229","authenticated-orcid":false,"given":"Lazar","family":"Milenkovi\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cuong","family":"Than","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,12,1]]},"reference":[{"key":"803_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Goldberg, A.V., Malkhi, D.: Routing in networks with low doubling dimension. In: Proc. of 26th ICDCS, p. 75 (2006)","DOI":"10.1109\/ICDCS.2006.72"},{"key":"803_CR2","doi-asserted-by":"publisher","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing. PODC \u201906, pp. 188\u2013197 (2006). https:\/\/doi.org\/10.1145\/1146381.1146411. Full version: https:\/\/www.cse.huji.ac.il\/~ittaia\/papers\/AG-TR.pdf","DOI":"10.1145\/1146381.1146411"},{"issue":"6","key":"803_CR3","doi-asserted-by":"publisher","first-page":"3026","DOI":"10.1016\/j.aim.2011.08.003","volume":"228","author":"I Abraham","year":"2011","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Advances in metric embedding theory. Adv. Math. 228(6), 3026\u20133126 (2011)","journal-title":"Adv. Math."},{"key":"803_CR4","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Chang, H.-C., Raghvendra, S., Xiao, A.: Deterministic, near-linear $$\\varepsilon $$-approximation algorithm for geometric bipartite matching. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1052\u20131065 (2022)","DOI":"10.1145\/3519935.3519977"},{"issue":"1","key":"803_CR5","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/s0097539792224474","volume":"24","author":"N Alon","year":"1995","unstructured":"Alon, N., Karp, R.M., Peleg, D., West, D.: A graph-theoretic game and its application to the $$k$$-server problem. SIAM J. Comput. 24(1), 78\u2013100 (1995). https:\/\/doi.org\/10.1137\/s0097539792224474","journal-title":"SIAM J. Comput."},{"key":"803_CR6","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Halvorsen, E.B., Larsen, K.G.: Near-optimal labeling schemes for nearest common ancestors. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 972\u2013982 (2014). SIAM","DOI":"10.1137\/1.9781611973402.72"},{"issue":"1","key":"803_CR7","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry 9(1), 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"key":"803_CR8","doi-asserted-by":"crossref","unstructured":"Andoni, A., Zhang, H.: Sub-quadratic (1+$$\\backslash $$eps)-approximate Euclidean Spanners, with Applications (2023)","DOI":"10.1109\/FOCS57990.2023.00014"},{"key":"803_CR9","doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, pp. 489\u2013498 (1995)","DOI":"10.1145\/225058.225191"},{"issue":"2","key":"803_CR10","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/0405013","volume":"5","author":"B Awerbuch","year":"1992","unstructured":"Awerbuch, B., Peleg, D.: Routing with polynomial communication-space trade-off. SIAM J. Discret. Math. 5(2), 151\u2013162 (1992). https:\/\/doi.org\/10.1137\/0405013","journal-title":"SIAM J. Discret. Math."},{"issue":"11","key":"803_CR11","doi-asserted-by":"publisher","first-page":"2934","DOI":"10.1109\/26.328973","volume":"42","author":"B Awerbuch","year":"1994","unstructured":"Awerbuch, B., Kutten, S., Peleg, D.: On buffer-economical store-and-forward deadlock prevention. IEEE Trans. Commun. 42(11), 2934\u20132937 (1994)","journal-title":"IEEE Trans. Commun."},{"key":"803_CR12","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jcss.2022.06.001","volume":"130","author":"Y Bartal","year":"2022","unstructured":"Bartal, Y., Fandina, O.N., Neiman, O.: Covering metric spaces by few trees. J. Comput. Syst. Sci. 130, 26\u201342 (2022)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"803_CR13","doi-asserted-by":"publisher","first-page":"2411","DOI":"10.1137\/22M1502707","volume":"36","author":"S Bhore","year":"2022","unstructured":"Bhore, S., T\u00f3th, C.D.: Euclidean steiner spanners: Light and sparse. SIAM J. Discret. Math. 36(3), 2411\u20132444 (2022)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"803_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/PL00009390","volume":"20","author":"TM Chan","year":"1998","unstructured":"Chan, T.M.: Approximate nearest neighbor queries revisited. Discret. Comput. Geom. 20(3), 359\u2013373 (1998)","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"803_CR15","first-page":"1","volume":"12","author":"T-HH Chan","year":"2016","unstructured":"Chan, T.-H.H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. ACM Transactions on Algorithms (TALG) 12(4), 1\u201322 (2016)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"803_CR16","doi-asserted-by":"crossref","unstructured":"Chang, H., Conroy, J., Le, H., Milenkovic, L., Solomon, S., Than, C.: Covering planar metrics (and beyond): O(1) trees suffice. In: FOCS, pp. 2231\u20132261. IEEE, USA (2023)","DOI":"10.1109\/FOCS57990.2023.00139"},{"key":"803_CR17","doi-asserted-by":"crossref","unstructured":"Chang, H., Conroy, J., Le, H., Milenkovic, L., Solomon, S., Than, C.: Shortcut partitions in minor-free graphs: Steiner point removal, distance oracles, tree covers, and more. In: SODA, pp. 5300\u20135331. SIAM, USA (2024)","DOI":"10.1137\/1.9781611977912.191"},{"key":"803_CR18","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.: Approximating a finite metric by a small number of tree metrics. In: Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pp. 379\u2013388 (1998). IEEE","DOI":"10.1109\/SFCS.1998.743488"},{"issue":"1","key":"803_CR19","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/S089548010444167X","volume":"20","author":"FF Dragan","year":"2006","unstructured":"Dragan, F.F., Yan, C., Lomonosov, I.: Collective tree spanners of graphs. SIAM J. Discret. Math. 20(1), 240\u2013260 (2006)","journal-title":"SIAM J. Discret. Math."},{"key":"803_CR20","doi-asserted-by":"crossref","unstructured":"Erickson, J., Van Der\u00a0Hoog, I., Miltzow, T.: Smoothing the gap between np and er. SIAM Journal on Computing (0), 20\u2013102 (2022)","DOI":"10.1137\/20M1385287"},{"key":"803_CR21","doi-asserted-by":"publisher","unstructured":"Fortune, S., Van\u00a0Wyk, C.J.: Efficient exact arithmetic for computational geometry. In: Proceedings of the Ninth Annual Symposium on Computational Geometry. SCG \u201993, pp. 163\u2013172. Association for Computing Machinery, New York, NY, USA (1993). https:\/\/doi.org\/10.1145\/160985.161015","DOI":"10.1145\/160985.161015"},{"key":"803_CR22","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in trees. In: ICALP. Lecture Notes in Computer Science, vol. 2076, pp. 757\u2013772. Springer, USA (2001)","DOI":"10.1007\/3-540-48224-5_62"},{"key":"803_CR23","doi-asserted-by":"publisher","unstructured":"Freedman, O., Gawrychowski, P., Nicholson, P.K., Weimann, O.: Optimal distance labeling schemes for trees. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (2017). https:\/\/doi.org\/10.1145\/3087801.3087804","DOI":"10.1145\/3087801.3087804"},{"key":"803_CR24","unstructured":"Gao, Z., Har-Peled, S.: Almost optimal locality sensitive orderings in Euclidean space. CoRR abs\/2310.12792 (2023)"},{"issue":"1","key":"803_CR25","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85\u2013112 (2004). https:\/\/doi.org\/10.1016\/j.jalgor.2004.05.002","journal-title":"J. Algorithms"},{"key":"803_CR26","doi-asserted-by":"publisher","unstructured":"Gottlieb, L., Roditty, L.: Improved algorithms for fully dynamic geometric spanners and geometric routing. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA\u201908, pp. 591\u2013600 (2008). https:\/\/doi.org\/10.5555\/1347082.1347148","DOI":"10.5555\/1347082.1347148"},{"key":"803_CR27","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: FOCS, pp. 534\u2013543. IEEE Computer Society, USA (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"803_CR28","doi-asserted-by":"publisher","unstructured":"Gupta, A., Kumar, A., Rastogi, R.: Traveling with a Pez dispenser (or, routing issues in MPLS). In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science,FOCS\u2019 01 (2001). https:\/\/doi.org\/10.1109\/sfcs.2001.959889","DOI":"10.1109\/sfcs.2001.959889"},{"key":"803_CR29","doi-asserted-by":"crossref","unstructured":"Kahalon, O., Le, H., Milenkovi\u0107, L., Solomon, S.: Can\u2019t see the forest for the trees: navigating metric spaces by bounded hop-diameter spanners. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pp. 151\u2013162 (2022)","DOI":"10.1145\/3519270.3538414"},{"issue":"4","key":"803_CR30","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1007\/s00039-005-0527-6","volume":"15","author":"R Krauthgamer","year":"2005","unstructured":"Krauthgamer, R., Lee, J.R., Mendel, M., Naor, A.: Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal. 15(4), 839\u2013858 (2005). https:\/\/doi.org\/10.1007\/s00039-005-0527-6","journal-title":"Geom. Funct. Anal."},{"key":"803_CR31","doi-asserted-by":"crossref","unstructured":"Le, H., Solomon, S.: Truly optimal Euclidean spanners. SIAM Journal on Computing (0), 19\u2013135 (2022)","DOI":"10.1137\/20M1317906"},{"issue":"1","key":"803_CR32","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jlap.2004.07.006","volume":"64","author":"C Li","year":"2005","unstructured":"Li, C., Pion, S., Yap, C.-K.: Recent progress in exact geometric computation. J. Logic Algebraic Program. 64(1), 85\u2013111 (2005)","journal-title":"J. Logic Algebraic Program."},{"issue":"1","key":"803_CR33","first-page":"51","volume":"24","author":"GA Margulis","year":"1988","unstructured":"Margulis, G.A.: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problemy Peredachi informatsii 24(1), 51\u201360 (1988)","journal-title":"Problemy Peredachi informatsii"},{"key":"803_CR34","doi-asserted-by":"publisher","unstructured":"Mendel, M., Naor, A.: Ramsey partitions and proximity data structures. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u2019 06) (2006). https:\/\/doi.org\/10.1109\/focs.2006.65","DOI":"10.1109\/focs.2006.65"},{"key":"803_CR35","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, USA (2007)"},{"issue":"3","key":"803_CR36","doi-asserted-by":"publisher","first-page":"167","DOI":"10.5555\/1379811.1379818","volume":"33","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Proximity-preserving labeling schemes. J. Graph Theory 33(3), 167\u2013176 (2000). https:\/\/doi.org\/10.5555\/1379811.1379818","journal-title":"J. Graph Theory"},{"key":"803_CR37","doi-asserted-by":"crossref","unstructured":"Salesin, D., Stolfi, J., Guibas, L.: Epsilon geometry: building robust algorithms from imprecise computations. In: Proceedings of the Fifth Annual Symposium on Computational Geometry, pp. 208\u2013217 (1989)","DOI":"10.1145\/73833.73857"},{"issue":"1","key":"803_CR38","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1093\/comjnl\/28.1.5","volume":"28","author":"N Santoro","year":"1985","unstructured":"Santoro, N., Khatib, R.: Labelling and implicit routing in networks. Comput. J. 28(1), 5\u20138 (1985)","journal-title":"Comput. J."},{"key":"803_CR39","unstructured":"Smid, M.: Notes on Binary Dumbbell Trees. Unpublished notes (2012)"},{"key":"803_CR40","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"key":"803_CR41","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA, pp. 1\u201310. ACM, USA (2001)","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"803_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. Journal of the ACM (JACM) 52(1), 1\u201324 (2005)","journal-title":"Journal of the ACM (JACM)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00803-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-025-00803-9","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00803-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T14:49:43Z","timestamp":1772462983000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-025-00803-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,1]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["803"],"URL":"https:\/\/doi.org\/10.1007\/s00454-025-00803-9","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,1]]},"assertion":[{"value":"28 October 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}