Inspection by Polygon Containment

We investigate the probelm of whether one polygon P can be translated to fit inside another polygon P. We obtain algorithms that run in O (n2log n) time in the case where P is convex and P is nonconvex and in the case where both polygons are rectilinearly convex. The parameter n is the sum of the number of bounding edges in the two polygons. Our algorithms compute the boundary of the feasible region, that is, the set of positions in which P fits inside P without touching P. Both algorithms are nearly optimal in the sense that the feasible region may have Omega (n2) edges.