Convex Polygon Containment: Improving Quadratic to Near Linear Time

Timothy M. Chan, Isaac M. Hair

We revisit a standard polygon containment problem: given a convex $k$-gon $P$ and a convex $n$-gon $Q$ in the plane, find a placement of $P$ inside $Q$ under translation and rotati…