moving a polygon around the corner in a corridor
We consider the problem of moving an n vertex simple polygon around a corner in a right-angular corridor. We give an &Ogr; ( n log n ) algorithm for a convex polygon which constructs a motion of the polygon when one exists; otherwise it reports that none exists. In the case of non-convex polygons, we have an &Ogr; ( n 2 ) time algorithm.
polygon log algorithm motion case timing