Please use this identifier to cite or link to this item:

Computing the maximum overlap of two convex polygons under translations

Authors De Berg, Mark
Cheong, Otfried
Devillers, Olivier
Van Kreveld, Marc
Teillaud, Monique
Issue Date 1998
Source Theory of computing, v. 31, (5), 1998, September , p. 613-628
Summary 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<sup>2</sup>+m<sup>2</sup>+min(nm<sup>2</sup>+n<sup>2</sup>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. As an upper bound, we show an example where the overlap in this placement is 4/9 of the maximum possible overlap.
Language English
Format Technical report
Files in this item:
File Description Size Format
199808.pdf 297.78 kB Adobe PDF