On translational motion planning in 3-space

ABSTRACT

Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A1,…,Ak with pairwise disjoint interiors. The free configuration space (space of all collision-free placements) of B can be represented as the complement of the union of the Minkowski sums Pi=Ai ⊕ (−B), for i=1,…,k. We show that the combinatorial complexity of the free configuration space of B is O(nklog2k), where n is the total complexity of the individual Minkowski sums P1,…,Pk. The bound is almost tight in the worst case. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nklog3k).

REFERENCES

• 1: B. Aronov and M. Shark, The common exterior of convex polygons in the plane, manuscript, 1994.
• 2: B. Aronov and M. Shark, Triangles in space, or building (and analyzing) castles in the air, Combinatorica 10(2) (1990), 137-173.
• 3: Boris Aronov , Micha Sharir, Castles in the air revisited, Proceedings of the eighth annual symposium on Computational geometry, p.146-156, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142710]
• 4: B. Aronov and M. Sharir, The union of convex polyhedra in three dimensions, Proc. 34th IEEE Syrup. on Foundation of Computer Science, 1993, pp. 518-529.
• 5: Mark de Berg , Jiří Matoušek , Otfried Schwarzkopf, Piecewise linear paths among convex obstacles, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.505-514, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167224]
• 6: Bernard Chazelle, An optimal algorithm for intersecting three-dimensional convex polyhedra, SIAM Journal on Computing, v.21 n.4, p.671-696, Aug. 1992 [doi>10.1137/0221041]
• 7: Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir , Jack Snoeyink, Computing a face in an arrangement of line segments and related problems, SIAM Journal on Computing, v.22 n.6, p.1286-1302, Dec. 1993 [doi>10.1137/0222077]
• 8: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 9: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 10: H. Edelsbrunner, L. Guibas, and M. Shark, The upper envelope of piecewise hnear functions: Algorithms and applications, Discrete Comput. Geom. 4 (1989), 311-336.
• 11: M. Greenberg and J. Harper, Algebraic Topology: A First Course, Benjamin-Cummings, Reading, MA, 1981.
• 12: L. Guibas, D. Knuth, and M. Sharir, Randomized incremental construction of Voronoi and Delaunay diagrams, Algorithmica 7 (1992), 381-413.
• 13: L. Guibas and R. Seidel, Computing convolutions by reciprocal search, Discrete Gomput. Geom. 2 (1987), 175- 193.
• 14: Dan Halperin , Chee-Keng Yap, Combinatorial complexity of translating a box in polyhedral 3-space, Proceedings of the ninth annual symposium on Computational geometry, p.29-37, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.160992]
• 15: G. Hotz and J. Sellen, On algebraic computation trees and Betti numbers, Manuscript, 1993.
• 16: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 17: N. Miller and M. Sharir, Efficient randomized algorithms for constructing the union of fat triangles and of pseudo-disks, manuscript, 1991.
• 18: J. Milnor, Morse Theory, Princeton University Press, Princeton, N J, 1963.
• 19: J. Pach and M. Sharir, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis, Discrete Comput. Geom. 4 (1989), 291-309.
• 20: M. Sharir, Efficient algorithms for planning purely translational collision-free motion in two and three dimensions, Proc. IEEE Syrup. on Robotics and Automation, 1987, pp. 1326-1331,
• 21: j.W. Vick, Homology Theory: An Introduction to Algebraic Topology, Academic Press, New York, 1973.

INDEX TERMS

Primary 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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory, Verification