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

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

Pankaj K. Agarwal, Kyle Fox and Oren Salzman
Conference Paper, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1179-1192, January, 2016

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

We study a path-planning problem amid a set O of obstacles in ℝ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 eps ∊ (0, 1]. Our algorithm computes in time O(frac{n^2}{eps^2} log (n/eps)) a path of total cost at most (1 + eps) times the cost of the optimal path.

BibTeX Reference
@conference{Agarwal-2016-5298,
title = {An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles},
author = {Pankaj K. Agarwal and Kyle Fox and Oren Salzman},
booktitle = {Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
month = {January},
year = {2016},
pages = {1179-1192},
}
2017-09-13T10:38:31+00:00