{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:11:17Z","timestamp":1763467877908,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540877431"},{"type":"electronic","value":"9783540877448"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-87744-8_40","type":"book-chapter","created":{"date-parts":[[2008,8,30]],"date-time":"2008-08-30T09:20:52Z","timestamp":1220088052000},"page":"478-489","source":"Crossref","is-referenced-by-count":31,"title":["An Optimal Dynamic Spanner for Doubling Metric Spaces"],"prefix":"10.1007","author":[{"given":"Lee-Ad","family":"Gottlieb","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liam","family":"Roditty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"40_CR1","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S. Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Nathanyahu, S., Silverman, R., Yu, A.Y.: An optimal algorithm for approximate nearest neighbor searching in fixed dimension. Journal of the ACM\u00a045(6), 891\u2013923 (1998)","journal-title":"Journal of the ACM"},{"key":"40_CR2","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0925-7721(99)00014-0","volume":"13","author":"S. Arya","year":"1999","unstructured":"Arya, S., Mount, D.M., Smid, M.: Dynamic algorithms for geometric spanners of small diameter: Randomized solutions. Computational Geometry: Theory and Applications\u00a013, 91\u2013107 (1999)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"40_CR3","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.comgeo.2004.01.003","volume":"28","author":"P. Bose","year":"2004","unstructured":"Bose, P., Gudmundsson, J., Morin, P.: Ordered theta graphs. Computational Geometry: Theory and Applications\u00a028, 11\u201318 (2004)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"40_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. J. ACM\u00a042, 67\u201390 (1995)","journal-title":"J. ACM"},{"key":"40_CR5","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.: Searching dynamic point sets in spaces with bounded doubling dimension. In: ACM Symposium on Theory of Computing (2006)","DOI":"10.1145\/1132516.1132599"},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"Gao, J., Guibas, L., Nguyen, A.: Deformable spanners and applications. In: ACM Symposium on Computational Geometry (2004)","DOI":"10.1145\/997817.997848"},{"key":"40_CR7","doi-asserted-by":"crossref","unstructured":"Gottlieb, L., Roditty, L.: Improved algorithms for fully dynamic geometric spanners and geometric routing. In: ACM Symposium on Discrete Algorithms (2008)","DOI":"10.1145\/1247069.1247134"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In (IEEE) Symposium on Foundations of Computer Science, pp. 534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"issue":"5","key":"40_CR9","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 J. Comput.\u00a035(5), 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"key":"40_CR10","unstructured":"Krauthgamer, R., Lee, J.: Navigating nets: Simple algorithms for proximity search. In: ACM-SIAM Symposium on Discrete Algorithms (2004)"},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"Roditty, L.: Fully dynamic geometric spanners. In: ACM Symposium on Computational Geometry (2007)","DOI":"10.1145\/1247069.1247134"},{"issue":"2","key":"40_CR12","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1142\/S0218195991000098","volume":"1","author":"J.S. Salowe","year":"1991","unstructured":"Salowe, J.S.: Constructing multidimensional spanner graphs. Int. J. Comput. Geometry Appl.\u00a01(2), 99\u2013107 (1991)","journal-title":"Int. J. Comput. Geometry Appl."},{"key":"40_CR13","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":"40_CR14","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF02574695","volume":"6","author":"P.M. Vaidya","year":"1991","unstructured":"Vaidya, P.M.: A sparse graph almost as good as the complete graph on points in K dimensions. Discrete & Computational Geometry\u00a06, 369\u2013381 (1991)","journal-title":"Discrete & Computational Geometry"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2008"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87744-8_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T19:05:24Z","timestamp":1738350324000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-87744-8_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540877431","9783540877448"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87744-8_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}