{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T06:14:13Z","timestamp":1781849653956,"version":"3.54.5"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T00:00:00Z","timestamp":1270598400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,1]]},"DOI":"10.1007\/s00453-010-9397-x","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T05:08:07Z","timestamp":1270616887000},"page":"66-80","source":"Crossref","is-referenced-by-count":3,"title":["Making Doubling Metrics Geodesic"],"prefix":"10.1007","volume":"59","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,4,7]]},"reference":[{"issue":"4","key":"9397_CR1","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 R n . Bull. Soc. Math. France 111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. France"},{"key":"9397_CR2","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: The 23rd International Conference on Machine Learning (ICML) (2006)","DOI":"10.1145\/1143844.1143857"},{"issue":"2","key":"9397_CR3","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1137\/S0097539701395978","volume":"34","author":"G. C\u0103linescu","year":"2004\/2005","unstructured":"C\u0103linescu, G., Karloff, H., Rabani, Y.: Approximation algorithms for the 0-extension problem. SIAM J. Comput. 34(2), 358\u2013372 (2004\/2005)","journal-title":"SIAM J. Comput."},{"key":"9397_CR4","unstructured":"Chan, T.-H.H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0762\u2013771 (2005)"},{"issue":"1","key":"9397_CR5","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/PL00009449","volume":"22","author":"K.L. Clarkson","year":"1999","unstructured":"Clarkson, K.L.: Nearest neighbor queries in metric spaces. Discrete Comput. Geom. 22(1), 63\u201393 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"9397_CR6","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A.: Searching dynamic point sets in spaces with bounded doubling dimension. In: The Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC) (2006)","DOI":"10.1145\/1132516.1132599"},{"key":"9397_CR7","first-page":"257","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J. Fakcharoenphol","year":"2003","unstructured":"Fakcharoenphol, J., Harrelson, C., Rao, S., Talwar, K.: An improved approximation algorithm for the 0-extension problem. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 257\u2013265. SIAM, Philadelphia (2003)"},{"key":"9397_CR8","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low\u2013distortion embeddings. In: Proceedings of the 44th Symposium on the Foundations of Computer Science (FOCS), pp.\u00a0534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"issue":"5","key":"9397_CR9","doi-asserted-by":"crossref","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. 35(5), 1148\u20131184 (2006) (electronic)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9397_CR10","doi-asserted-by":"crossref","DOI":"10.1145\/1273340.1273347","volume":"3","author":"P. Indyk","year":"2007","unstructured":"Indyk, P., Naor, A.: Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms 3(3), 31 (2007), 12\u00a0pp.","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"9397_CR11","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF02764938","volume":"54","author":"W.B. Johnson","year":"1986","unstructured":"Johnson, W.B., Lindenstrauss, J., Schechtman, G.: Extensions of Lipschitz maps into Banach spaces. Isr. J. Math. 54(2), 129\u2013138 (1986)","journal-title":"Isr. J. Math."},{"issue":"1","key":"9397_CR12","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1006\/eujc.1997.0154","volume":"19","author":"A. Karzanov","year":"1998","unstructured":"Karzanov, A.: Minimum 0-extensions of graph metrics. Eur. J. Comb. 19(1), 71\u2013101 (1998)","journal-title":"Eur. J. Comb."},{"key":"9397_CR13","unstructured":"Konjevod, G., Richa, A.W., Xia, D.: Optimal scale-free compact routing schemes in doubling networks. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA) (2007)"},{"key":"9397_CR14","first-page":"798","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"R. Krauthgamer","year":"2004","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 798\u2013807. SIAM, Philadelphia (2004)"},{"issue":"2\u20133","key":"9397_CR15","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/j.tcs.2005.09.017","volume":"348","author":"R. Krauthgamer","year":"2005","unstructured":"Krauthgamer, R., Lee, J.R.: The black-box complexity of nearest-neighbor search. Theor. Comput. Sci. 348(2\u20133), 262\u2013276 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"11","key":"9397_CR16","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1016\/j.crma.2004.03.005","volume":"338","author":"J.R. Lee","year":"2004","unstructured":"Lee, J.R., Naor, A.: Absolute Lipschitz extendability. C. R. Math. Acad. Sci. Paris 338(11), 859\u2013862 (2004)","journal-title":"C. R. Math. Acad. Sci. Paris"},{"issue":"5","key":"9397_CR17","doi-asserted-by":"crossref","first-page":"1609","DOI":"10.1007\/s00039-008-0689-0","volume":"18","author":"J.R. Lee","year":"2009","unstructured":"Lee, J.R., Naor, A., Peres, Y.: Trees and Markov convexity. Geom. Funct. Anal. 18(5), 1609\u20131659 (2009)","journal-title":"Geom. Funct. Anal."},{"issue":"1","key":"9397_CR18","first-page":"99","volume":"31","author":"J. Matou\u0161ek","year":"1990","unstructured":"Matou\u0161ek, J.: Extension of Lipschitz mappings on metric trees. Comment. Math. Univ. Carol. 31(1), 99\u2013104 (1990)","journal-title":"Comment. Math. Univ. Carol."},{"issue":"2","key":"9397_CR19","doi-asserted-by":"crossref","first-page":"337","DOI":"10.4171\/RMI\/201","volume":"12","author":"S. Semmes","year":"1996","unstructured":"Semmes, S.: On the nonexistence of bi-Lipschitz parameterizations and geometric problems about A \u221e-weights. Rev. Mat. Iberoam. 12(2), 337\u2013410 (1996)","journal-title":"Rev. Mat. Iberoam."},{"key":"9397_CR20","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low-dimensional metrics. In: Proceedings of the 36th ACM Symposium on the Theory of Computing (STOC), pp.\u00a0281\u2013290 (2004)","DOI":"10.1145\/1007352.1007399"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9397-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9397-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9397-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:05Z","timestamp":1559137505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9397-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,7]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["9397"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9397-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,7]]}}}