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

dc.contributor.authorAgarwal, P. K.
dc.contributor.authorFox, Kyle J.
dc.contributor.authorSalzman, O.
dc.contributor.utdAuthorFox, Kyle J.
dc.date.accessioned2019-06-28T18:33:00Z
dc.date.available2019-06-28T18:33:00Z
dc.date.created2018-08
dc.description.abstractWe 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.
dc.description.departmentErik Jonsson School of Engineering and Computer Science
dc.description.sponsorshipNSF 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.
dc.identifier.bibliographicCitationAgarwal, P. K., K. J. Fox, and O. Salzman. 2018. "An efficient algorithm for computing high-quality paths amid polygonal obstacles." ACM Transactions on Algorithms 14(4): art. 46, doi:10.1145/3230650
dc.identifier.issn1549-6325
dc.identifier.issue4
dc.identifier.urihttps://hdl.handle.net/10735.1/6634
dc.identifier.volume14
dc.language.isoen
dc.publisherAssociation for Computing Machinery
dc.relation.urihttp://dx.doi.org/10.1145/3230650
dc.rights©2018 ACM
dc.source.journalACM Transactions on Algorithms
dc.subjectApproximation theory
dc.subjectGeometry
dc.subjectPolynomials
dc.titleAn Efficient Algorithm for Computing High-Quality Paths Amid Polygonal Obstacles
dc.type.genrearticle

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
JECS-6559-9609.02-LINK.pdf
Size:
165.18 KB
Format:
Adobe Portable Document Format
Description:
Link to Article

Collections