Making doubling metrics geodesic

Anupam Gupta, Kunal Talwar

Research output: Contribution to journalArticlepeer-review


The starting point of our research is the following problem: given a doubling metric M=(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 M, and the shortest-path distances in G′ closely approximate those of M when restricted to V×V. Similar results are shown when the metric M is an additive (tree) metric and the graph G′ is restricted to be a tree.

Original languageEnglish (US)
Pages (from-to)66-80
Number of pages15
JournalAlgorithmica (New York)
Issue number1
StatePublished - Jan 2011


  • Convex closure
  • Doubling metrics
  • Geodesic metrics
  • Low-distortion embeddings
  • Metric embeddings

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Making doubling metrics geodesic'. Together they form a unique fingerprint.

Cite this