s'authentifier
version française rss feed

inria-00073859, version 1

Computing the Maximum Overlap of Two Convex Polygons Under Translations

Mark De Berg 1, Olivier Devillers (), Marc Van Kreveld, Otfried Schwarzkopf, Monique Teillaud ()

N° RR-2832 (1996)

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.

  • Domaine : Informatique/Autre
  • Mots-clés : COMPUTATIONAL GEOMETRY / ARRANGEMENT / LOCALISATION
  • Référence interne : RR-2832
 
  • inria-00073859, version 1
  • oai:hal.inria.fr:inria-00073859
  • Contributeur : 
  • Soumis le : Mercredi 24 Mai 2006, 13:55:42
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:28
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...