Computing the Maximum Overlap of Two Convex Polygons Under Translations.

Mark De Berg (1) , Olivier Devillers (2) , Marc Van Kreveld (1) , Otfried Schwarzkopf (1) , Monique Teillaud (2)

1 Department of Information and Computing Sciences [Utrecht]
2 PRISME - Geometry, Algorithms and Robotics

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^2m)), 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 position which translates the centroid of Q on the centroid of P always realizes an overlap of 9/25 of the maximum overlap and that this overlap may be as small as 4/9 of the maximum.

Domaines: Géométrie algorithmique [cs.CG]

Mark De Berg, Olivier Devillers, Marc Van Kreveld, Otfried Schwarzkopf, Monique Teillaud. Computing the Maximum Overlap of Two Convex Polygons Under Translations.. Theory of Computing Systems, 1998, 31, pp.613-628. ⟨10.1007/PL00005845⟩. ⟨inria-00413175⟩