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

It is proposed to estimate time complexity of motion planning algorithms in terms of both the problem size and the tightness parameter; the latter is intuitively the amount of scaling of the movable object which turns the problem from solvable to unsolvable or conversely. An algorithm for motion planning of the rectangle in the plane amidst polygonal obstacles with the complexity \(O(((a/b)(1/t)+1)n\log^ 2 n)\) is proposed, where \(t\) is for tightness. For ``non-tight'' problems, this significantly improves the known \(\Omega(n^ 2)\) upper bounds. As a technical contribution, the complexities of boundaries of unions of some simple figures are presented. This leads to \(O((1/a)n\log^ 2 n)\) motion planning for a rectangle which may be rotated by angles less than \(a\).