Maximum Overlap Area of Several Convex Polygons Under Translations

Abstract

Let $k\ge 2$ be a constant. Given any $k$ convex polygons in the plane with a total of $n$ vertices, we present an $O(n{\log }^{2k-3}n)$ time algorithm that finds a translation of each of the polygons such that the area of intersection of the $k$ polygons is maximized. Given one such placement, we also give an $O(n)$ time algorithm which computes the set of all translations of the polygons which achieve this maximum.