COMPUTING THE MAXIMUM OVERLAP OF 2 CONVEX POLYGONS UNDER TRANSLATIONS

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 co mbinatorially distinct placements of Q with respect to P under transla tions 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 up per bound, we show an example where the overlap in this placement is 4 /9 of the maximum possible overlap,=.