{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T17:46:04Z","timestamp":1759513564095},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642034558"},{"type":"electronic","value":"9783642034565"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03456-5_19","type":"book-chapter","created":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T02:39:16Z","timestamp":1251772756000},"page":"275-289","source":"Crossref","is-referenced-by-count":13,"title":["The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension"],"prefix":"10.1007","author":[{"given":"Michiel","family":"Smid","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","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.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"key":"19_CR2","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P. Assouad","year":"1983","unstructured":"Assouad, P.: Plongements lipschitziens dans \u211d\n                    N\n                  . Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France\u00a0111, 429\u2013448 (1983)","journal-title":"Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France"},{"unstructured":"Bose, P., Carmi, P., Farshi, M., Maheshwari, A., Smid, M.: Computing the greedy spanner in near-quadratic time. To appear in Algorithmica","key":"19_CR3"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P.B. 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. Journal of the ACM\u00a042, 67\u201390 (1995)","journal-title":"Journal of the ACM"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1142\/S0218195995000088","volume":"5","author":"B. Chandra","year":"1995","unstructured":"Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. International Journal of Computational Geometry & Applications\u00a05, 125\u2013144 (1995)","journal-title":"International Journal of Computational Geometry & Applications"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"1998","DOI":"10.1137\/S0097539793251244","volume":"28","author":"B. Chandra","year":"1999","unstructured":"Chandra, B., Karloff, H., Tovey, C.: New results on the old k-opt algorithm for the traveling salesman problem. SIAM Journal on Computing\u00a028, 1998\u20132029 (1999)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Das, G., Heffernan, P., Narasimhan, G.: Optimally sparse spanners in 3-dimensional Euclidean space. In: Proceedings of the 9th ACM Symposium on Computational Geometry, pp. 53\u201362 (1993)","key":"19_CR7","DOI":"10.1145\/160985.160998"},{"unstructured":"Das, G., Narasimhan, G., Salowe, J.: A new way to weigh malnourished Euclidean graphs. In: Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 215\u2013222 (1995)","key":"19_CR8"},{"key":"19_CR9","doi-asserted-by":"publisher","first-page":"1479","DOI":"10.1137\/S0097539700382947","volume":"31","author":"J. Gudmundsson","year":"2002","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Fast greedy algorithms for constructing sparse geometric spanners. SIAM Journal on Computing\u00a031, 1479\u20131500 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S. Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM Journal on Computing\u00a035, 1148\u20131184 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0131-8","volume-title":"Lectures on Analysis on Metric Spaces","author":"J. Heinonen","year":"2001","unstructured":"Heinonen, J.: Lectures on Analysis on Metric Spaces. Springer, Berlin (2001)"},{"key":"19_CR12","doi-asserted-by":"publisher","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","volume":"44","author":"S. Lin","year":"1965","unstructured":"Lin, S.: Computer solutions of the traveling salesman problem. Bell Systems Technical Journal\u00a044, 2245\u20132269 (1965)","journal-title":"Bell Systems Technical Journal"},{"key":"19_CR13","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, Cambridge (2007)"},{"key":"19_CR14","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1988","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Berlin (1988)"},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/BF02574005","volume":"11","author":"J. Soares","year":"1994","unstructured":"Soares, J.: Approximating Euclidean distances by small degree graphs. Discrete & Computational Geometry\u00a011, 213\u2013233 (1994)","journal-title":"Discrete & Computational Geometry"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02187718","volume":"4","author":"P.M. Vaidya","year":"1989","unstructured":"Vaidya, P.M.: An O(n logn) algorithm for the all-nearest-neighbors problem. Discrete & Computational Geometry\u00a04, 101\u2013115 (1989)","journal-title":"Discrete & Computational Geometry"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A.C. Yao","year":"1982","unstructured":"Yao, A.C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing\u00a011, 721\u2013736 (1982)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Efficient Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03456-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T16:29:58Z","timestamp":1552148998000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03456-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642034558","9783642034565"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03456-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}