Computing the maximum overlap of two convex polygons under translations

Abstract

Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices, We prove that the maximum number of combinatorially distinct placements of Q with respect to P under translations is O (n(2) + m(2) + min(nm(2) + n(2)m)), and we give an example showing that this bound is tight in the worst case. Second, we present an O((n + m) log(n + m)) algorithm for determining a translation of Q that maximizes the area of overlap of P and Q, We also prove that the placement of Q that makes the centroids of Q and P coincide realizes an overlap of at least 9/25 of the maximum possible overlap. Pls an upper bound, we show an example where the overlap in this placement is 4/9 of the maximum possible overlap,=.