Maximum Overlap Area of Several Convex Polygons Under Translations

07/01/2023

∙

by   Hyuk Jun Kweon, et al.

∙

0

∙

share

Let k ≥ 2 be a constant. Given any k convex polygons in the plane with a total of n vertices, we present an O(nlog^2k-3n) 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.