An efficient algorithm for computing high-quality paths amid polygonal obstacles
Journal Article (Journal Article)
We study a path-planning problem amid a set O of obstacles in R , 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( log ) a path of total cost at most (1 + ε) times the cost of the optimal path. 2 n 2 n ε 2 ε
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Kyle, FOX; Salzman, O
Published Date
- August 1, 2018
Published In
Volume / Issue
- 14 / 4
Electronic International Standard Serial Number (EISSN)
- 1549-6333
International Standard Serial Number (ISSN)
- 1549-6325
Digital Object Identifier (DOI)
- 10.1145/3230650
Citation Source
- Scopus