TY - CHAP

T1 - Approximate Shortest Homotopic Paths in Weighted Regions

AU - Cheng, Siu-Wing

AU - Jin, Jiongxin

AU - Vigneron, Antoine E.

AU - Wang, Yajun

N1 - KAUST Repository Item: Exported on 2020-04-23
Acknowledgements: Department of Computer Science and Engineering, HKUST, Hong Kong
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2010

Y1 - 2010

N2 - Let P be a path between two points s and t in a polygonal subdivision T with obstacles and weighted regions. Given a relative error tolerance ε ∈(0,1), we present the first algorithm to compute a path between s and t that can be deformed to P without passing over any obstacle and the path cost is within a factor 1 + ε of the optimum. The running time is O(h 3/ε2 kn 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. © 2010 Springer-Verlag.

AB - Let P be a path between two points s and t in a polygonal subdivision T with obstacles and weighted regions. Given a relative error tolerance ε ∈(0,1), we present the first algorithm to compute a path between s and t that can be deformed to P without passing over any obstacle and the path cost is within a factor 1 + ε of the optimum. The running time is O(h 3/ε2 kn 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. © 2010 Springer-Verlag.

UR - http://hdl.handle.net/10754/597601

UR - http://link.springer.com/10.1007/978-3-642-17514-5_10

UR - http://www.scopus.com/inward/record.url?scp=78650858803&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17514-5_10

DO - 10.1007/978-3-642-17514-5_10

M3 - Chapter

SN - 9783642175138

SP - 109

EP - 120

BT - Lecture Notes in Computer Science

PB - Springer Nature

ER -