Making Doubling Metrics Geodesic
Making Doubling Metrics Geodesic
复制标题
使度量加倍测地线
DOI：
10.1007/s00453-010-9397-x
复制
发表时间：
2010
期刊：
影响因子：
1.1
通讯作者：
Kunal Talwar
中科院分区：
文献类型：
--
作者：
Anupam Gupta;Kunal Talwar
我们的研究出发点是这样一个问题：给定一个加倍度量<$N =（V，d），能否（有效地）找到一个V <$V′的无权图G′=（V′，E′），它的最短路度量d′仍然加倍，并且与V×V上的d一致？虽然很容易证明，如果距离必须精确保持，则上述问题的答案是否定的。然而，允许d和d′之间的（1+ε）失真使我们能够绕过这个障碍，并且获得具有最多因子O（log ε−1）乘以G的加倍维数的未加权图G′。更一般地，本文给出了构造图G′的算法，其凸（或测地）闭包的双倍维数接近于G ′的双倍维数，当G ′限制为V×V时，G′中的最短路距离接近于G ′中的最短路距离.当度量G ′是一个可加的（树）度量且图G′被限制为树时，也得到了类似的结果。
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.