On the general motion planning problem with two degrees of freedom
Leo J. Guibas, Micha Sharir, Shmuel Sifrony · 1988
We show that, under reasonable assumptions, any collision-avoiding motion planning problem for a moving system with two degrees of freedom can be solved in time Ο(λs(n) log2n), where n is the number of collision constraints imposed on the system, s is a fixed parameter depending e.g. on the maximum algebraic degree of these constraints, and λs(n) is the (almost linear) maximum length of (n,s) Davenport Schinzel sequences. This follows from an upper bound of Ο(λs(n)) that we establish for the combinatorial complexity of a single connected component of the space of all free placements of the moving system. Although our study is motivated by motion planning, it is actually a study of topological, combinatorial, and algorithmic issues involving a single face in an arrangement of curves. Our results thus extend beyond the area of motion planning, and have applications in many other areas.