Motion planning for a convex polygon in a polygonal environment

We study the motion-planning problem for a convex m-gon P in a planar polyg onal environment Q bounded by n edges. We give the first algorithm that con structs the entire free configuration space (the three-dimensional space of all free placements of P in Q), in time that is near-quadratic in mit, whi ch is nearly optimal in the worst case. The algorithm is also conceptually simple. Previous solutions were incomplete, more expensive, or produced onl y part of the free configuration space. Combining our solution with paramet ric searching, we obtain an algorithm that finds the largest placement of P in Q in time that is also near-quadratic in mn. In addition, we describe a n algorithm that preprocesses the computed free configuration space so that reachability queries can be answered in polylogarithmic time.