On monotone paths among obstacles with applications to planning assemblies

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.