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 304925 B Adobe PDF