An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles

We study a path-planning problem amid a set ℴ of obstacles in ℝ 2, in which we wish to compute a short path between two points while also maintaining a high clearance from ℴ; the clearance of a point is its distance from a nearest obstacle in ℴ. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let n be the total number of obstacle vertices and let ∊ ∊ (0, 1]. Our algorithm computes in time a path of total cost at most (1 + ∊ ) times the cost of the optimal path.

Authors

• Pankaj K. Agarwal
• Kyle Fox
• Oren Salzman

Keywords

No keywords are indexed for this paper.