caa a22 4500 445804742 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s00453-010-9397-x doi (NATIONALLICENCE)springer-10.1007/s00453-010-9397-x Making Doubling Metrics Geodesic [Elektronische Daten] [Anupam Gupta, Kunal Talwar] The starting point of our research is the following problem: given a doubling metric ℳ=(V,d), can one (efficiently) find an unweighted graph G′=(V′,E′) with V⊆V′ whose shortest-path metric d′ is still doubling, and which agrees with d on V×V? While it is simple to show that the answer to the above question is negative if distances must be preserved exactly. However, allowing a (1+ε) distortion between d and d′ enables us bypass this hurdle, and obtain an unweighted graph G′ with doubling dimension at most a factor O(log ε −1) times the doubling dimension of G. More generally, this paper gives algorithms that construct graphs G′ whose convex (or geodesic) closure has doubling dimension close to that of ℳ, and the shortest-path distances in G′ closely approximate those of ℳ when restricted to V×V. Similar results are shown when the metric ℳ is an additive (tree) metric and the graph G′ is restricted to be a tree. Springer Science+Business Media, LLC, 2010 Metric embeddings nationallicence Low-distortion embeddings nationallicence Doubling metrics nationallicence Geodesic metrics nationallicence Convex closure nationallicence Gupta Anupam Computer Science Department, Carnegie Mellon University, 15213, Pittsburgh, PA, USA aut Talwar Kunal Microsoft Research, Silicon Valley Campus, 1065 La Avenida, 94043, Mountain View, CA, USA aut Algorithmica Springer-Verlag 59/1(2011-01-01), 66-80 0178-4617 59:1<66 2011 59 453 https://doi.org/10.1007/s00453-010-9397-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9397-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Gupta Anupam Computer Science Department, Carnegie Mellon University, 15213, Pittsburgh, PA, USA aut NATIONALLICENCE 700 1- Talwar Kunal Microsoft Research, Silicon Valley Campus, 1065 La Avenida, 94043, Mountain View, CA, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/1(2011-01-01), 66-80 0178-4617 59:1<66 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer