×
Agarwal, Pankaj K.; Fox, Kyle; Salzman, Oren

An efficient algorithm for computing high-quality paths amid polygonal obstacles. (English) Zbl 1454.68150

ACM Trans. Algorithms 14, No. 4, Article No. 46, 21 p. (2018).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W25 Approximation algorithms

Keywords:

motion planning; approximation; bicriteria objective; computational geometry
Cite Review PDF
Full Text: DOI

References:

[1] Pankaj K. Agarwal and Hongyan Wang. 2000. Approximation algorithms for curvature-constrained shortest paths. SIAM J. Comput. 30, 6 (2000), 1739-1772. · Zbl 0980.68145
[2] Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee. 2013. Voronoi Diagrams and Delaunay Triangulations. World Scientific. · Zbl 1295.52001
[3] John F. Canny and John H. Reif. 1987. New lower bound techniques for robot motion planning problems. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 49-60.
[4] 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.
[5] Danny Z. Chen, Ovidiu Daescu, and Kevin S. Klenk. 2001. On geometric path query problems. Int. J. Comput. Geometry Appl. 11, 6 (2001), 617-645. · Zbl 1074.68632
[6] Danny Z. Chen and Haitao Wang. 2013. Computing shortest paths among curved obstacles in the plane. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 369-378. · Zbl 1305.68218
[7] 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. · Zbl 1081.68700
[8] Kenneth L. Clarkson. 2006. Building triangulations using epsilon-nets. In ACM Symposium on Theory of Computing. 326-335. · Zbl 1301.68238
[9] Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Donald R. Sheehy, and Ameya Velingker. 2015. Approximating nearest neighbor distances. In Proceedings of the 14th Annual Symposium on Algorithms and Data Structures. Springer, 200-211. · Zbl 1444.68276
[10] Michael L. Fredman and Robert Endre Tarjan. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 3 (1987), 596-615. · Zbl 1412.68048
[11] Dan Halperin, Oren Salzman, and Micha Sharir. 2017. Algorithmic motion planning. In Handbook of Discrete and Computational Geometry (3rd ed.), C. D. Tóth, J. O’Rourke, and J. E. Goodman (Eds.). CRC Press LLC, 1311-1342.
[12] Monika Rauch Henzinger, Philip N. Klein, Satish Rao, and Sairam Subramanian. 1997. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55, 1 (1997), 3-23. · Zbl 0880.68099
[13] John Hershberger, Subhash Suri, and Hakan Yıldız. 2013. A near-optimal algorithm for shortest paths among curved obstacles in the plane. In Proceedings of the 29th Annual Symposium on Computational Geometry. 359-368. · Zbl 1305.68239
[14] Niel Lebeck, Thomas Mølhave, and Pankaj K. Agarwal. 2013. Computing highly occluded paths on a terrain. In Proceedings of the 21st Annual ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 14-23.
[15] Joseph S. B. Mitchell. 2017. Shortest paths and networks. In Handbook of Discrete and Computational Geometry (3rd ed.), C. D. Tóth, J. O’Rourke, and J. E. Goodman (Eds.). CRC Press LLC, 811-848.
[16] Joseph S. B. Mitchell, Günter Rote, and Gerhard J. Woeginger. 1992. Minimum-link paths among obstacles in the plan. Algorithmica 8, 5 8 6 (1992), 431-459. · Zbl 0788.68144
[17] Colm Ó’Dúnlaing and Chee-Keng Yap. 1985. A “retraction” method for planning the motion of a disc. J. Algo. 6, 1 (1985), 104-111. · Zbl 0556.68051
[18] 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.
[19] Ron Wein, Jur P. van den Berg, and Dan Halperin. 2007. The visibility-Voronoi complex and its applications. Comput. Geom. 36, 1 (2007), 66-87. · Zbl 1110.65021
[20] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.