Computing the maximum overlap of two convex polygons under translations

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(2)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. Pls an upper bound, we show an example where the overlap in this placement is 4/9 of the maximum possible overlap,=.
Publisher
SPRINGER VERLAG
Issue Date
1998
Language
ENG
Keywords

ALGORITHM

Citation

THEORY OF COMPUTING SYSTEMS, v.31, no.5, pp.613 - 628

ISSN
1432-4350
URI
http://hdl.handle.net/10203/322
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
1996-33.pdf(790.86 kB)Download
  • Hit : 456
  • Download : 199
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 23 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0