An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space. (English) Zbl 0688.68039

Let B be a convex polygon of k vertices and k edges. B is free to move (translate and rotate) in an open two-dimensional area bounded by a collection of polygonal obstacles having altogether n corners. The problem is to plan a continuous obstacle-avoiding motion of B from a given initial place to a given final place. The authors presented an algorithm with time-complexity O(kn \(\lambda_ 6(kn)\log kn)\), where \(\lambda_ s(q)\) is an almost linear function of q yielding the maximal number of connected portion of q continuous functions which compose the graph of their lower envelope, under the condition tht each pair of these functions intersect in at most s points. This is an elegant result.
Reviewer: Du Ding-Zhu


68Q25 Analysis of algorithms and problem complexity
68U99 Computing methodologies and applications
Full Text: DOI EuDML


[1] M. Atallah, Dynamic computational geometry,Proc. 24th Symp. on Foundations of Computer Science, 1983, pp. 92-99.
[2] B. K. Bhattacharya and J. Zorbas, Solving the two-dimensional findpath problem using a line-triangle representation of the robot. Tech. Rept., School of Computing Science, Simon Fraser University, Burnaby, B.C. V5A 1S6. · Zbl 0662.68119
[3] L. Guibas, L. Ramshaw, and J. Stolfi, A kinetic framework for computational geometry,Proc. 24th IEEE Symp. on Foundations of Computer Science, 1983, pp. 100-111.
[4] S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica6(2) (1986), 151-177. · Zbl 0636.05003 · doi:10.1007/BF02579170
[5] K. Kedem, R. Livne, J. Pach, and M. Sharir, On the union of Jordan regions and collision-free translational motion admist polygonal obstacles,Discrete Comput. Geom.1 (1986), 59-71. · Zbl 0594.52004 · doi:10.1007/BF02187683
[6] K. Kedem and M. Sharir, An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles,Proc. ACM Symp. on Computational Geometry, 1985, pp. 75-80.
[7] D. Leven and M. Sharir, An efficient and simple motion-planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers,J. Algorithms8 (1987), 192-215. · Zbl 0643.68050 · doi:10.1016/0196-6774(87)90038-1
[8] D. Leven and M. Sharir, Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams,Discrete Comput. Geom.2 (1987), 9-31. · Zbl 0606.52002 · doi:10.1007/BF02187867
[9] D. Leven and M. Sharir, On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space,Discrete Comput. Geom.2 (1987) 255-270. · Zbl 0616.52009 · doi:10.1007/BF02187883
[10] C. Ó’Dúnlaing, M. Sharir, and C. Yap, Generalized Voronoi diagrams for a ladder: I. Topological analysis,Comm. Pure Appl. Math.39 (1986), 423-483. · Zbl 0601.51025 · doi:10.1002/cpa.3160390402
[11] C. Ó’Dúnlaing, M. Sharir, and C. Yap, Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram,Algorithmica2 (1987), 27-59. · Zbl 0631.68042 · doi:10.1007/BF01840348
[12] C. Ó’Dúnlaing and C. Yap, A “retraction” method for planning the motion of a disc,J. Algorithms6 (1985), 104-111. · Zbl 0556.68051 · doi:10.1016/0196-6774(85)90021-5
[13] J. O’Rourke, Lower bounds for moving a ladder, Tech. Rept. 85/20, Department of EECS, The Johns Hopkins University, 1985.
[14] Th. Ottmann, P. Widmayer, and D. Wood, A fast algorithm for boolean mask operations, Rept. No. 112, Inst. f. Angewandte Mathematik und Formale Beschreibungsverfahren, D-7500 Karlsruhe, 1982. · Zbl 0495.68095
[15] J. T. Schwartz and M. Sharir, On the piano movers’ problem: I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers,Comm. Pure Appl. Math.36 (1983), 345-398. · Zbl 0554.51007 · doi:10.1002/cpa.3160360305
[16] M. Sharir, Almost linear upper bounds on the length of general Davenport-Schinzel sequences,Combinatorica7 (1987), 131-143. · Zbl 0636.05004 · doi:10.1007/BF02579209
[17] M. Sharir, Improved lower bounds on the length of Davenport-Schinzel sequences,Combinatorica8 (1988), to appear. · Zbl 0672.05015
[18] S. Sifrony and M. Sharir, A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space,Algorithmica2 (1987), 367-402. · Zbl 0643.68049 · doi:10.1007/BF01840368
[19] E. Szemeredi, On a problem by Davenport and Schinzel,Acta Arith.25 (1974), 213-224. · Zbl 0291.05003
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.