Approximate shortest homotopic paths in weighted regions

Siuwing Cheng, Jiongxin Jin, Antoine E. Vigneron, Yajun Wang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


A path P between two points s and t in a polygonal subdivision T with obstacles and weighted regions defines a class of paths that can be deformed to P without passing over any obstacle. We present the first algorithm that, given P and a relative error tolerance ε (0, 1), computes a path from this class with cost at most 1 + ε times the optimum. The running time is O(h 3/ε 2kn polylog (k,n,1/ε)), where k is the number of segments in P and h and n are the numbers of obstacles and vertices in T, respectively. The constant in the running time of our algorithm depends on some geometric parameters and the ratio of the maximum region weight to the minimum region weight. © 2012 World Scientific Publishing Company.
Original languageEnglish (US)
Pages (from-to)83-102
Number of pages20
JournalInternational Journal of Computational Geometry & Applications
Issue number01
StatePublished - Sep 12 2012

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computational Mathematics
  • Geometry and Topology
  • Theoretical Computer Science
  • Applied Mathematics


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

Cite this