Approximate shortest paths in anisotropic regions

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

11 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 all ϵ ∈ (0, 1), and for any two points vs and vd, we give an algorithm that finds a path from vs to vd whose cost is at most (1 + ϵ) times the minimum cost. 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)
Title of host publicationProceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
PublisherAssociation for Computing Machinery
Number of pages9
ISBN (Electronic)9780898716245
StatePublished - 2007
Externally publishedYes
Event18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States
Duration: Jan 7 2007Jan 9 2007


Other18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Country/TerritoryUnited States
CityNew Orleans

ASJC Scopus subject areas

  • Software
  • General Mathematics


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

Cite this