An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles
Abstract
We study a path-planning problem amid a set O of obstacles in R 2 , in which we wish to compute a short path between two points while also maintaining a high clearance from O; the clearance of a point is its distance from a nearest obstacle in O. 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 O ( n 2 /ε 2 log n /ε) a path of total cost at most (1 + ε) times the cost of the optimal path.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 21, 2018
- Source ID
- 10.1145/3230650
Entities
People
- Kyle Fox
- Oren Salzman
- Pankaj Agarwal
Organizations
- Carnegie Mellon University
- Duke University
- Israel Science Foundation
- National Science Foundation
- Office of Naval Research
- University of Texas at Dallas