APPROXIMATE SHORTEST HOMOTOPIC PATHS IN WEIGHTED REGIONS
Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron, Yajun Wang · International Journal of Computational Geometry & Applications · 2012
A path P between two points s and t in a polygonal subdivision [Formula: see text] 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 [Formula: see text], where k is the number of segments in P and h and n are the numbers of obstacles and vertices in [Formula: see text], 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.