{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:27:40Z","timestamp":1760441260633},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,2,24]],"date-time":"2015-02-24T00:00:00Z","timestamp":1424736000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2015,3]]},"DOI":"10.1007\/s00454-015-9663-4","type":"journal-article","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T11:01:45Z","timestamp":1424689305000},"page":"296-326","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Average Stretch Factor: How Low Does It Go?"],"prefix":"10.1007","volume":"53","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"9663_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I. , Bartal, Y., Chan, H.T.-H., Dhamdhere, K., Gupta, A., Kleinberg, J.M., Neiman, O., Slivkins, A.: Metric embeddings with relaxed guarantees. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 83\u2013100. IEEE Computer Society, Washington, DC (2005)","DOI":"10.1109\/SFCS.2005.51"},{"key":"9663_CR2","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. In: Bansal, N., Pruhs, K., Stein, C. (eds.) Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 502\u2013511. SIAM, Philadelphia (2007)"},{"issue":"1","key":"9663_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1239\/aap\/1208358883","volume":"40","author":"DJ Aldous","year":"2008","unstructured":"Aldous, D.J., Kendall, W.S.: Short-length routes in low-cost networks via Poisson line patterns. Adv. Appl. Probab 40(1), 1\u201321 (2008)","journal-title":"Adv. Appl. Probab"},{"key":"9663_CR4","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. Wiley, Hoboken (2008)","edition":"3"},{"key":"9663_CR5","doi-asserted-by":"crossref","unstructured":"Bender, M. A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of Latin American Theoretical Informatics (LATIN 2000), pp. 88\u201394 (2000)","DOI":"10.1007\/10719839_9"},{"issue":"5","key":"9663_CR6","first-page":"214","volume":"23","author":"JL Bentley","year":"1978","unstructured":"Bentley, J.L.: Multidimensional divide-and-conquer. Commun. ACM 23(5), 214\u2013228 (1978)","journal-title":"Commun. ACM"},{"key":"9663_CR7","doi-asserted-by":"crossref","unstructured":"Bose, P., Dujmovi\u0107, V., Morin, P., Smid, M.: Robust geometric spanners. In: Proceedings of the Twenty-Ninth ACM Symposium on Computational Geometry (SoCG 2013). ACM Press, New York (2013)","DOI":"10.1145\/2462356.2462381"},{"key":"9663_CR8","unstructured":"Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, pp. 291\u2013300 (1993)"},{"issue":"1","key":"9663_CR9","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"PB Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42(1), 67\u201390 (1995)","journal-title":"J. ACM"},{"key":"9663_CR10","first-page":"196","volume":"3","author":"P Carmi","year":"2012","unstructured":"Carmi, P., Smid, M.: An optimal algorithm for computing angle-constrained spanners. J. Comput. Geom. 3, 196\u2013221 (2012)","journal-title":"J. Comput. Geom."},{"key":"9663_CR11","doi-asserted-by":"crossref","unstructured":"Elkin, M., Solomon, S.: Steiner shallow-light trees are exponentially lighter than spanning ones. In: Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science, pp. 373\u2013382 (2011)","DOI":"10.1109\/FOCS.2011.18"},{"key":"9663_CR12","unstructured":"Eppstein, D.: Spanning trees and spanners. Technical Report 96-16, Department of Information and Computer Science, University of California, Irvine. http:\/\/www.ics.uci.edu\/eppstein\/pubs\/Epp-TR-96-16.pdf (1996)"},{"key":"9663_CR13","first-page":"425","volume-title":"Handbook of Computational Geometry (Chap. 9)","author":"D Eppstein","year":"1999","unstructured":"Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry (Chap. 9), pp. 425\u2013461. Elsevier, Amsterdam (1999)"},{"key":"9663_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0131-8","volume-title":"Lectures on Analysis on Metric Spaces. Universitext","author":"J Heinonen","year":"2001","unstructured":"Heinonen, J.: Lectures on Analysis on Metric Spaces. Universitext. Springer-Verlage, New York (2001)"},{"key":"9663_CR15","doi-asserted-by":"crossref","unstructured":"Lueker, G.S.: A data structure for orthogonal range queries. In: Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS\u201978), pp. 28\u201334. IEEE Computer Society, Long Beach, CA (1978)","DOI":"10.1109\/SFCS.1978.1"},{"key":"9663_CR16","doi-asserted-by":"crossref","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, New York (2007)"},{"key":"9663_CR17","unstructured":"Ruppert, J., Seidel, R.: Approximating the $$d$$ d -dimensional complete Euclidean graph. In: Proceedings of the 3rd Canadian Conference on Computational Geometry (CCCG 1991), pp. 207\u2013210 (1991)"},{"key":"9663_CR18","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1142\/S0218195991000098","volume":"1","author":"JS Salowe","year":"1991","unstructured":"Salowe, J.S.: Constructing multidimensional spanner graphs. Int. J. Comput. Geom. Appl. 1, 99\u2013107 (1991)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9663_CR19","doi-asserted-by":"crossref","unstructured":"Solomon, S.: Personal Communication with M. Smid (2012)","DOI":"10.4324\/9780203147832"},{"key":"9663_CR20","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF02574695","volume":"6","author":"PM Vaidya","year":"1991","unstructured":"Vaidya, P.M.: A sparse graph almost as good as the complete graph on points in $$K$$ K dimensions. Discrete Comput. Geom. 6, 369\u2013381 (1991)","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9663-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-015-9663-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9663-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T00:53:29Z","timestamp":1566348809000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-015-9663-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,24]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["9663"],"URL":"https:\/\/doi.org\/10.1007\/s00454-015-9663-4","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,24]]}}}