Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/695
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. 613628  
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.  
Subjects  
Language  English 

Format  Technical report  
Access 
Files in this item:
