inria-00413175, version 1
Computing the Maximum Overlap of Two Convex Polygons Under Translations.
Mark De Berg 1Olivier Devillers
2Marc Van Kreveld 1Otfried Schwarzkopf 1Monique Teillaud
a, 2
Theory of Computing Systems 31 (1998) 613-628
Résumé : 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^2+m^2+min(nm^2+n^2m)), 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 position which translates the centroid of Q on the centroid of P always realizes an overlap of 9/25 of the maximum overlap and that this overlap may be as small as 4/9 of the maximum.
- a – INRIA
- 1 : Department of Information and Computing Sciences
- Utrecht University
- 2 : PRISME (INRIA Sophia Antipolis)
- INRIA
- Domaine : Informatique/Géométrie algorithmique
- inria-00413175, version 1
- http://hal.inria.fr/inria-00413175
- oai:hal.inria.fr:inria-00413175
- Contributeur : Olivier Devillers
- Soumis le : Jeudi 3 Septembre 2009, 13:50:40
- Dernière modification le : Jeudi 3 Septembre 2009, 14:18:09






Documents associés
Exporter