A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

Timothy M. Chan, Isaac M. Hair

Given two convex polygons $P$ and $Q$ with $n$ and $m$ edges, the maximum overlap problem is to find a translation of $P$ that maximizes the area of its intersection with $Q$. We g…