Maximizing the overlap of two planar convex sets under rigid motions

Hee Kap Ahn, Otfried Cheong*, Chong Dae Park, Chan Su Shin, Antoine Vigneron

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any >0, we compute a rigid motion such that the area of overlap is at least 1- times the maximum possible overlap. Our algorithm uses O(1/) extreme point and line intersection queries on P and Q, plus O((1/ 2)log(1/)) running time. If only translations are allowed, the extra running time reduces to O((1/)log(1/)). If P and Q are convex polygons with n vertices in total that are given in an array or balanced tree, the total running time is O((1/)logn+(1/2)log(1/)) for rigid motions and O((1/)logn+(1/)log(1/)) for translations.

Original languageEnglish (US)
Pages (from-to)3-15
Number of pages13
JournalComputational Geometry: Theory and Applications
Issue number1 SPEC. ISS.
StatePublished - May 2007


  • Approximation algorithm
  • Convex shape
  • Geometric pattern matching
  • Sublinear algorithm

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Cite this