{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T18:47:04Z","timestamp":1790189224371,"version":"4.1.0"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>In a seminal STOC 1995 paper, Arya et al. conjectured that spanners for low-dimensional Euclidean spaces with constant maximum degree, hop-diameter $O(\\log n)$, and lightness $O(\\log n)$ (i.e., weight $O(\\log n) \\cdot w({MST}))$ can be constructed in $O(n \\log n)$ time. This conjecture, which became a central open question in this area, was resolved in the affirmative by Elkin and Solomon in STOC 2013. In fact, Elkin and Solomon proved that the conjecture of Arya et al. holds even in doubling metrics. However, Elkin and Solomon's spanner construction is complicated. In this work we present a significantly simpler construction of spanners for doubling metrics with the same guarantees as above. Our construction is based on the basic net-tree spanner framework. However, by employing well-known properties of the net-tree spanner in conjunction with numerous new ideas, we managed to get significantly stronger results. First and foremost, our construction extends in a simple and natural way to provide $k$-fault tolerant spanners with maximum degree $O(k^2)$, hop-diameter $O(\\log n)$, and lightness $O(k^2 \\log n)$. This is the first construction of fault-tolerant spanners (even for Euclidean metrics) that achieves good bounds (polylogarithmic in $n$ and polynomial in $k$) on all the involved parameters simultaneously. Second, we show that the lightness bound of our construction can be improved to $O(k^2)$ (with high probability), for random points in $[0,1]^D$, where $2 \\le D = O(1)$.<\/jats:p>","DOI":"10.1137\/130930984","type":"journal-article","created":{"date-parts":[[2015,2,10]],"date-time":"2015-02-10T11:05:47Z","timestamp":1423566347000},"page":"37-53","source":"Crossref","is-referenced-by-count":17,"title":["New Doubling Spanners: Better and Simpler"],"prefix":"10.1137","volume":"44","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mingfei","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Li","family":"Ning","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,2,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"S. P. A. Alewijnse, Q. W. Bouts, A. P. ten Brink, and K. Buchin,\n                      Distribution-Sensitive Construction of the Greedy Spanner\n                      , CoRR, arXiv:1401.1085, 2014.","DOI":"10.1007\/978-3-662-44777-2_6"},{"key":"atypb2","first-page":"489","author":"Arya S.","year":"1995","journal-title":"Proceedings of STOC"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"atypb4","first-page":"291","author":"Callahan P. B.","year":"1993","journal-title":"Proceedings of SODA"},{"key":"atypb5","first-page":"762","author":"Chan H. T.-H.","year":"2005","journal-title":"Proceedings of SODA"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"H. T.H. Chan, M. Li, and L. Ning,\n                      Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree\n                      , in Proceedings of ICALP, 2012.","DOI":"10.1007\/978-3-642-31594-7_16"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9115-5"},{"key":"atypb8","unstructured":"T.H. H. Chan, M. Li, and L. Ning,\n                      Incubators vs zombies: Fault-tolerant, short, thin and lanky spanners for doubling metrics\n                      , CoRR, arXiv:1207.0892, 2012."},{"key":"atypb9","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1145\/10515.10534","author":"Chew P.","year":"1986","journal-title":"Proceedings of Symposium on Computational Geometry"},{"key":"atypb10","first-page":"56","author":"Clarkson K. L.","year":"1987","journal-title":"Proceedings of STOC"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"atypb13","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1145\/1132516.1132599","author":"Cole R.","year":"2006","journal-title":"Proceedings of STOC"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1121-7"},{"key":"atypb15","first-page":"132","author":"Das G.","year":"1994","journal-title":"Proceedings of Symposium on Computational Geometry"},{"key":"atypb16","first-page":"519","author":"Dinitz Y.","year":"2008","journal-title":"Proceedings of FOCS"},{"key":"atypb17","first-page":"215","author":"Elkin M.","year":"2009","journal-title":"Proceedings of ESA"},{"key":"atypb18","first-page":"645","author":"Elkin M.","year":"2013","journal-title":"Proceedings of STOC"},{"key":"atypb19","first-page":"190","author":"Gao J.","year":"2004","journal-title":"Proceedings of Symposium on Computational Geometry"},{"key":"atypb20","first-page":"591","author":"Gottlieb L.-A.","year":"2008","journal-title":"Proceedings of SODA"},{"key":"atypb21","first-page":"478","author":"Gottlieb L.-A.","year":"2008","journal-title":"Proceedings of ESA"},{"key":"atypb22","first-page":"534","author":"Gupta A.","year":"2003","journal-title":"Proceedings of FOCS"},{"key":"atypb23","first-page":"150","author":"Har-Peled S.","year":"2005","journal-title":"Proceedings of Symposium on Computational Geometry"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19487-8_23"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"G. Narasimhan and M. H. M. Smid,\n                      Geometric Spanner Networks\n                      , Cambridge University Press, Cambridge, UK, 2007.","DOI":"10.1017\/CBO9780511546884"},{"key":"atypb26","first-page":"373","author":"Roditty L.","year":"2007","journal-title":"Proceedings of Symposium on Computational Geometry"},{"key":"atypb27","unstructured":"S. Solomon,\n                      Fault-tolerant spanners for doubling metrics: Better and simpler\n                      , CoRR, arXiv:1207.7040, 2012."},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"S. Solomon,\n                      From hierarchical partitions to hierarchical covers: Optimal fault-tolerant spanners for doubling metrics\n                      , in Proceedings of STOC, 2014.","DOI":"10.1145\/2591796.2591864"},{"key":"atypb29","first-page":"48","volume":"1","author":"Solomon S.","year":"2010","journal-title":"Proceedings of ESA"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130930984","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:16:25Z","timestamp":1787336185000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130930984"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130930984"],"URL":"https:\/\/doi.org\/10.1137\/130930984","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}