{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T18:44:53Z","timestamp":1761417893763,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T00:00:00Z","timestamp":1534809600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-09-40671,CCF-10-12254,CCF-11-61359,IIS-14-08846,CCF-15-13816,IIS-14-09003"],"award-info":[{"award-number":["CCF-09-40671,CCF-10-12254,CCF-11-61359,IIS-14-08846,CCF-15-13816,IIS-14-09003"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","award":["2012\/229"],"award-info":[{"award-number":["2012\/229"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"name":"German-Israeli Foundation","award":["1150-82.6\/2011"],"award-info":[{"award-number":["1150-82.6\/2011"]}]},{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Hermann Minkowski Minerva Center for Geometry at Tel Aviv University"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1102\/11"],"award-info":[{"award-number":["1102\/11"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Toyota Motor Engineering & Manufacturing"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>\n            We study a path-planning problem amid a set O of obstacles in R\n            <jats:sup>2<\/jats:sup>\n            , 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            <jats:italic>n<\/jats:italic>\n            be the total number of obstacle vertices and let \u03b5 \u2208 (0, 1]. Our algorithm computes in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/\u03b5\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            \/\u03b5) a path of total cost at most (1 + \u03b5) times the cost of the optimal path.\n          <\/jats:p>","DOI":"10.1145\/3230650","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T12:09:47Z","timestamp":1534853387000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles"],"prefix":"10.1145","volume":"14","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyle","family":"Fox","sequence":"additional","affiliation":[{"name":"The University of Texas at Dallas, Richardson, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oren","family":"Salzman","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/586841.586892"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","unstructured":"Franz Aurenhammer Rolf Klein and Der-Tsai Lee. 2013. Voronoi Diagrams and Delaunay Triangulations. World Scientific.","DOI":"10.5555\/2563475"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.42"},{"volume-title":"Proceedings of the Canadian Conference on Computational Geometry","author":"Nicholas","key":"e_1_2_1_4_1","unstructured":"Nicholas J. Cavanna and Donald R. Sheehy. 2016. Adaptive metrics for adaptive samples. In Proceedings of the Canadian Conference on Computational Geometry. Simon Fraser University, Vancouver, British Columbia, Canada."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000675"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462377"},{"volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementation","author":"Choset Howie","key":"e_1_2_1_7_1","unstructured":"Howie Choset, Kevin M. Lynch, Seth Hutchinson, George Kantor, Wolfram Burgard, Lydia E. Kavraki, and Sebastian Thrun. 2005. Principles of Robot Motion: Theory, Algorithms, and Implementation. MIT Press."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132564"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21840-3_17"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_11_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Halperin Dan","unstructured":"Dan Halperin, Oren Salzman, and Micha Sharir. 2017. Algorithmic motion planning. In Handbook of Discrete and Computational Geometry (3rd ed.), C. D. T\u00f3th, J. O\u2019Rourke, and J. E. Goodman (Eds.). CRC Press LLC, 1311--1342.","edition":"3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462374"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2525314.2525363"},{"key":"e_1_2_1_15_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Mitchell Joseph S. B.","unstructured":"Joseph S. B. Mitchell. 2017. Shortest paths and networks. In Handbook of Discrete and Computational Geometry (3rd ed.), C. D. T\u00f3th, J. O\u2019Rourke, and J. E. Goodman (Eds.). CRC Press LLC, 811--848.","edition":"3"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758855"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90021-5"},{"volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation. IEEE, 1500--1505","author":"Song Guang","key":"e_1_2_1_18_1","unstructured":"Guang Song, Shawna Miller, and Nancy M. Amato. 2001. Customizing PRM roadmaps at query time. In Proceedings of the IEEE International Conference on Robotics and Automation. IEEE, 1500--1505."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.11.007"},{"key":"e_1_2_1_20_1","first-page":"11","article-title":"Planning high-quality paths and corridors amidst obstacles","volume":"27","author":"Wein Ron","year":"2008","unstructured":"Ron Wein, Jur P. van den Berg, and Dan Halperin. 2008. Planning high-quality paths and corridors amidst obstacles. I. J. Robot. Res. 27, 11--12 (2008), 1213--1231.","journal-title":"I. J. Robot. Res."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3230650","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3230650","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3230650","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:47Z","timestamp":1750210787000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3230650"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,21]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3230650"],"URL":"https:\/\/doi.org\/10.1145\/3230650","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,8,21]]},"assertion":[{"value":"2017-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}