# An efficient algorithm for computing high-quality paths amid polygonal obstacles

Conference Paper

We study a path-planning problem amid a set 0 of obstacles in R2, in which we wish to compute a short path between two points while also maintaining a high clearance from 0; the clearance of a point is its distance from a nearest obstacle in 0. 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 0(n2/ϵ2 log n/ϵ) a path of total cost at most (1 + ϵ) times the cost of the optimal path.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Fox, K; Salzman, O

### Published Date

- January 1, 2016

### Published In

- Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

### Volume / Issue

- 2 /

### Start / End Page

- 1179 - 1192

### International Standard Book Number 13 (ISBN-13)

- 9781510819672

### Digital Object Identifier (DOI)

- 10.1137/1.9781611974331.ch82

### Citation Source

- Scopus