January
2016
An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles
Authors:
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.
copied = false, 2000);
">
@conference{Agarwal-2016-5298,
author = {Pankaj K. Agarwal And Kyle Fox And Oren Salzman},
title = {An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles},
booktitle = {Proceedings of 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16)},
year = {2016},
month = {January},
pages = {1179 - 1192},
}
author = {Pankaj K. Agarwal And Kyle Fox And Oren Salzman},
title = {An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles},
booktitle = {Proceedings of 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16)},
year = {2016},
month = {January},
pages = {1179 - 1192},
}