Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment

摘要

We consider the problem of planning the motion of an arbitrary k-sided polygonal robot B, free to translate and rotate in a polygonal environment V bounded by n edges. We show that the combinatorial complexity of a single connected component of the free configuration space of B is k/sup 3/n/sup 2/2/sup O(log(2/3)/ n). This is a significant improvement of the naive bound O((kn)/sup 3/); when k is constant, which is often the case in practice, this yields a near-quadratic bound on the complexity of such a component, which almost settles (in this special case) a long-standing conjecture regarding the complexity of a single cell in a three-dimensional arrangement of surfaces. We also present an algorithm that constructs a single component of the free configuration space of B in time O(n/sup 2+/spl epsi//), for any /spl epsi/>0, assuming B has a constant number of sides. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying motion planning problem, within the same asymptotic running time.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>