On monotone paths among obstacles with applications to planning assemblies

ABSTRACT

We study the class of problems associated with the detection and computation of monotone paths among a set of disjoint obstacles. We give an &Ogr;(nE) algorithm for finding a monotone path (if one exists) between two points in the plane in the presence of polygonal obstacles. (Here, E is the size of the visibility graph defined by the n vertices of the obstacles.) If all of the obstacles are convex, we prove that there always exists a monotone path between any two points s and t. We give an &Ogr;(n log n) algorithm for finding such a path for any s and t, after an initial &Ogr;(E + n log n) preprocesing. We introduce the notions of “monotone path map”, and “shortest monotone path map” and give algorithms to compute them. We apply our results to a class of separation and assembly problems, yielding polynomial-time algorithms for planning an assembly sequence (based on separations by single translations) of arbitrary polygonal parts in two dimensions.

REFERENCES

• CR: J. Canny and J. Reif, "New Lower Bound Techniques for Robot Motion Planning Problems" ) Proc. 28th FOCS, pp. 49-60, Oct. 1987.
• GM: S.K. Ghosh and D.M. Mount, "An Output Sensitive Algorithm for Computing Visibility Graphs" ) Technical Report CS-TR-1874, Department of Computer Science, University of Maryland, July 1987. (Also appears in FOCS, 1987.)
• GH: L. J. Guibas , J. Hershberger, Optimal shortest path queries in a simple polygon, Proceedings of the third annual symposium on Computational geometry, p.50-63, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41964]
• Gy: Leo J. Guibas , F. Frances Yao, On translating a set of rectangles, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.154-160, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804663]
• PS: F.P. Preparata and K.J. Supowit, "Testing a Simple Polygon for Monotonicity" , Information Processing Letters 12, No. 4 (1981), pp. 161-164.
• To: G .T. Toussaint , "Movable Separability of Sets", in Computational Geometry, Ed. G.T. Toussaint, North Holland Publishing Co., 1985.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory