TY - GEN

T1 - Approximate shortest homotopic paths in weighted regions

AU - Cheng, Siu Wing

AU - Jin, Jiongxin

AU - Vigneron, Antoine

AU - Wang, Yajun

N1 - Funding Information:
The research of Cheng and Jin was supported by the Research Grant Council, Hong Kong, China (project no. 612107).

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.

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.

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 - Conference contribution

AN - SCOPUS:78650858803

SN - 3642175163

SN - 9783642175169

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 109

EP - 120

BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings

T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -