{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T09:23:06Z","timestamp":1778664186920,"version":"3.51.4"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["87209011"],"award-info":[{"award-number":["87209011"]}]},{"name":"BSF","award":["2008430"],"award-info":[{"award-number":["2008430"]}]},{"name":"Lynn and William Frankel Center for Computer Sciences"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,11,2]]},"abstract":"<jats:p>\n            The degree, the (hop-)diameter, and the weight are the most basic and well-studied parameters of geometric spanners. In a seminal STOC'95 paper, titled \u201cEuclidean spanners: short, thin and lanky\u201d, Arya et al. [1995] devised a construction of Euclidean (1+\u03b5)-spanners that achieves constant degree, diameter\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ), weight\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) \u010b \u03c9(\n            <jats:italic>MST<\/jats:italic>\n            ), and has running time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \u010b log\n            <jats:italic>n<\/jats:italic>\n            ). This construction applies to\n            <jats:italic>n<\/jats:italic>\n            -point constant-dimensional Euclidean spaces. Moreover, Arya et al. conjectured that the weight bound can be improved by a logarithmic factor, without increasing the degree and the diameter of the spanner, and within the same running time.\n          <\/jats:p>\n          <jats:p>\n            This conjecture of Arya et al. became one of the most central open problems in the area of Euclidean spanners. Nevertheless, the only progress since 1995 towards its resolution was achieved in the lower bounds front: Any spanner with diameter\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) must incur weight \u03a9(log\n            <jats:italic>n<\/jats:italic>\n            ) \u010b \u03c9(\n            <jats:italic>MST<\/jats:italic>\n            ), and this lower bound holds regardless of the stretch or the degree of the spanner [Dinitz et al. 2008; Agarwal et al. 2005].\n          <\/jats:p>\n          <jats:p>\n            In this article we resolve the long-standing conjecture of Arya et al. in the affirmative. We present a spanner construction with the same stretch, degree, diameter, and running time, as in Arya et al.'s result, but with\n            <jats:italic>optimal weight<\/jats:italic>\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) \u010b \u03c9(\n            <jats:italic>MST<\/jats:italic>\n            ). So our spanners are as thin and lanky as those of Arya et al., but they are\n            <jats:italic>really<\/jats:italic>\n            short!\n          <\/jats:p>\n          <jats:p>\n            Moreover, our result is more general in three ways. First, we demonstrate that the conjecture holds true not only in constant-dimensional Euclidean spaces, but also in\n            <jats:italic>doubling metrics<\/jats:italic>\n            . Second, we provide a general trade-off between the three involved parameters, which is\n            <jats:italic>tight in the entire range<\/jats:italic>\n            . Third, we devise a transformation that decreases the lightness of spanners in\n            <jats:italic>general metrics<\/jats:italic>\n            , while keeping all their other parameters in check. Our main result is obtained as a corollary of this transformation.\n          <\/jats:p>","DOI":"10.1145\/2819008","type":"journal-article","created":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T17:09:35Z","timestamp":1446484175000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Optimal Euclidean Spanners"],"prefix":"10.1145","volume":"62","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.08.003"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 670--671","author":"Agarwal P. K."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225191"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365722"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Annual European Symposium on Algorithms. 48--59","author":"Arya S."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214038"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9293-4"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 70--78","author":"Chan H. T.-H."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 762--771","author":"Chan H. T.-H."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_27"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142717"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000088"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00280-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/10515.10534"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28402"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132599"},{"key":"e_1_2_1_20_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms 2nd ed. McGraw-Hill Book Company Boston MA.   T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms 2nd ed. McGraw-Hill Book Company Boston MA."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/160985.160998"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/177424.177579"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 215--222","author":"Das G."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.24"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Elkin M."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488691"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997848"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"L. Gottlieb A. Kontorovich and R. Krauthgamer. 2012. Efficient regression in metric space via approximate lipschitz extension. Manuscript.  L. Gottlieb A. Kontorovich and R. Krauthgamer. 2012. Efficient regression in metric space via approximate lipschitz extension. Manuscript.","DOI":"10.1007\/978-3-642-39140-8_3"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 591--600","author":"Gottlieb L."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_40"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 828--837","author":"Gudmundsson J.","year":"2002"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/646345.689916"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328921"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_42"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the Annual Symposium on Foundations of Computer Science. 534--543","author":"Gupta A."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/343477.343514"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/61764.61787"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187821"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 791--801","author":"Krauthgamer R."},{"key":"e_1_2_1_42_1","unstructured":"H. P. Lenhof J. S. Salowe and D. E. Wrege. 1994. New methods to mix shortest-path and minimum spanning trees. manuscript.  H. P. Lenhof J. S. Salowe and D. E. Wrege. 1994. New methods to mix shortest-path and minimum spanning trees. manuscript."},{"key":"e_1_2_1_43_1","first-page":"97","article-title":"An approximation algorithm for min-cost network design. DIMACS Series in Discr","volume":"53","author":"Mansour Y.","year":"2000","journal-title":"Math and TCS"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"G. Narasimhan and M. Smid. 2007. Geometric Spanner Networks. Cambridge University Press.   G. Narasimhan and M. Smid. 2007. Geometric Spanner Networks. Cambridge University Press.","DOI":"10.1017\/CBO9780511546884"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276868"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247069.1247134"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/109648.109677"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142716"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03456-5_19"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133101"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the Annual European Symposium on Algorithms. 48--59","author":"Solomon S."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574695"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2819008","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2819008","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:17Z","timestamp":1750223237000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2819008"}},"subtitle":["Really Short, Thin, and Lanky"],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":53,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,11,2]]}},"alternative-id":["10.1145\/2819008"],"URL":"https:\/\/doi.org\/10.1145\/2819008","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2012-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}