|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/695
|
| 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
Translations
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. |
| URI: | http://hdl.handle.net/1783.1/695 |
| Appears in Collections: | CSE TCSC Research Reports
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| 199808.pdf | | 297Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
