An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles

ABSTRACT

We state and prove a theorem about the number of points of local nonconvexity in the union of m. Minkowski sums of planar convex sets, and then apply it to planning a collision-free translational motion of a convex polygon B amidst several (convex) polygonal obstacles Al,…, Am, following a basic approach suggested by Lozano-Perez and Wesley. Assuming that the number of corners of B is fixed, the algorithm developed here runs in time &Ogr;(n log2n), where n is the total number of corners of the Al's.

REFERENCES

• 1: [Be] Benson, R. V., Euclidean Geometry and Convexity, McGraw-Hill, 1966, pp. 97- 113.
• 2: [BO] Bentley, J. L. and Ottmann, A., Algorithms for reporting and counting geometric intersections, IEEE Trans. on Computers, Vol C-28 (1979), pp. 643-647.
• 3: [GK] Guay, M. D. and Kay, D. C., On sets having finitely many points of local nonconvexity, Israel J. Math. 1970, pp. 39-52.
• 4: [GRS] Guibas, L., Ramshaw, L. and Stolfi J., A kinetic approach to computational geometry, Proc. 24th IEEE Symp. on Foundations of Computer Science, 1983, pp. 100-111.
• 5: [Ki] Kirkpatric, D. G., Optimal search in planar subdivisions, SIAM J. Computing, Vol 12, No. 1 (1983), pp. 28-35.
• 6: [LS] Leven, D. and Sharir, M., An efficient and simple motion planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers, Tech. Rept. 84-014, The Eskenasy Institute of Computer Science, Tel Aviv University, November 1984.
• 7: Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
• 8: J. Nievergelt , F. P. Preparata, Plane-sweep algorithms for intersecting geometric figures, Communications of the ACM, v.25 n.10, p.739-747, Oct 1982 [doi>10.1145/358656.358681]
• 9: [OY] O'Dunlaing, C. and Yap, C., A 'retraction' method for planning the motion of a disc, to appear in J. of Algorithms.
• 10: [OSY1] O'Dunlaing, C., Sharir, M. and Yap, C., Generalized Voronoi diagrams for a ladder: I. Topological considerations, Tech. Rept., Computer Science Dept., Courant Institute, 1984.
• 11: [OSY2] O'Dunlaing, C., Sharir, M. and Yap, C., Generalized Voronoi Diagrams for a Ladder: II. Efficient Construction of the Diagram, Tech. Rept., Computer Science Dept., Courant Institute, October 1984.
• 12: [OWW] Ottmann, Th., Widmeyer, P. and Wood, d., A fast algorithm for boolean mask operations, Inst. f. Angewandte Mathematik und Formale Beschreibungsverfahren, D-7500 Karlsruhe, Rept. No. 112, 1982.
• 13: [SS1] Schwartz, J. T. and Sharir, M., On the "Piano Movers" problem I. The case of a two dimensional rigid polygonal body moving amidst polygonal boundaries, Comm. Pure and Appl. Math. 35 (1983), pp. 345-398.
• 14: Micha Sharir , Amir Schorr, On shortest paths in polyhedral spaces, SIAM Journal on Computing, v.15 n.1, p.193-215, Feb. 1986 [doi>10.1137/0215014]
• 15: [We] Welzl, E., Constructing the visibility graph for n line segments in O(n²) time. Tech. Rept., Inst. of Appl. Math. and Comp. Science, University of Leiden, The Netherlands, 1984.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

General Terms:
Algorithms, Design, Performance, Theory