Approximate shortest paths in anisotropic regions*

Siu Wing Cheng*, Hyeon Suk Na, Antoine Vigneron, Yajun Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with n vertices. Let ρ ≤ 1 be a real number. Distances in each face of this subdivision are measured by a convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius 1/ρ. Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric. For any ε ε{lunate} (0, 1) and for any two points vs and vs we give an algorithm that finds a path from vs to vd whose cost is at most (1+ε) times the optimal. Our algorithm runs in O(ρ2 log ρ/ε2 n3 log (ρn/ε)) time. This bound does not depend on any other parameters; in particular it does not depend on the minimum angle in the subdivision. We give applications to two special cases that have been considered before: the weighted region problem and motion planning in the presence of uniform flows. For the weighted region problem with weights in [1, ρ] ∪ {∞}, the time bound of our algorithm improves to O(ρ logρ/ε n3 log (ρn/ε)).

Original languageEnglish (US)
Pages (from-to)802-824
Number of pages23
JournalSIAM Journal on Computing
Issue number3
StatePublished - 2008


  • Approximation algorithm
  • Computational geometry
  • Convex distance function
  • Shortest path
  • Weighted region

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Approximate shortest paths in anisotropic regions*'. Together they form a unique fingerprint.

Cite this