HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >

Please use this identifier to cite or link to this item:
Title: Computing the maximum overlap of two convex polygons under translations
Authors: De Berg, Mark
Cheong, Otfried
Devillers, Olivier
Van Kreveld, Marc
Teillaud, Monique
Keywords: Convex polygon
Combinatorially distinct placements
Maximum possible overlap
Issue Date: 1998
Citation: Theory of computing, v. 31, no. 5, September 1998, p. 613-628
Series/Report no.: HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-98-08
Abstract: 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(n2+m2+min(nm2+n2m)), 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.
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
199808.pdf297KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.