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

Date

ORCID

Journal Title

Journal ISSN

Volume Title

Publisher

Association for Computing Machinery

item.page.doi

Abstract

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(n²/ε² log n/ε) a path of total cost at most (1 + ε) times the cost of the optimal path.

Description

Keywords

Approximation theory, Geometry, Polynomials

item.page.sponsorship

NSF grants CCF-09- 40671, CCF-10-12254, CCF-11-61359, CCF-15-13816, IIS-14-08846, IIS-14-09003; U.S.-Israel Binational Science Foundation grant 2012/229; Israel Science Foundation grant 1102/11; German-Israeli Foundation grant 1150-82.6/2011.

Rights

©2018 ACM

Citation

Collections