| Federal Republic of Germany (2008) | |||||||||||||
Abstract | |||||||||||||
| Abstract: We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have running time f~(n 2) where n is the number of obstacle corners. We introduce the tightness of a motion planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with running time O((~-._.!_ _ + 1)n(logn)2), where a> b ecrlt are the lenghts of the sides of a rectangle and ~crit is the tightness of the problem. We show further that the complexity ( = number of vertices) of the boundary of n bow-ties (c.f. Figure 1.1) is O(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented. | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||