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 O(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 O(nlog n) algorithm for finding such a path for any s and t, after an initial O(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 (baaed on separations by single translations) of arbitrary polygonal parts in two dimensions.