Approximate shortest homotopic paths in weighted regions

S.W. Cheng, J. Jin, A. Vigneron, Y. Wang
International Journal of Computational Geometry and Applications, 22(1), 83-102, (2012)

Approximate shortest homotopic paths in weighted regions

Keywords

Shortest homotopic path

Abstract

​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(h3ε2knpolylog(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.

Code

DOI: 10.1007/978-3-642-17514-5_10

Sources

Website PDF

See all publications 2012