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

Kedem, K.; Sharir, M.

Discrete Comput. Geom. 5, No. 1, 43-75 (1990).

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

MSC:

68Q25	Analysis of algorithms and problem complexity
68U99	Computing methodologies and applications

Keywords:

polygon motion; time-complexity; computational geometry; polygonal obstacles

References:

[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