Approximate motion planning and the complexity of the boundary of the union of simple geometric figures

We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of (n ²), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with a running time ofO((a/b · 1/_crit + 1)n(logn)²), wherea b are the lengths 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 ofn bow ties (see Figure 1) isO(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.This work was supported partially by the DFG Schwerpunkt Datenstrukturen und Algorithmen, Grants Me 620/6 and Al 253/1, and by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM).