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

21 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

Bibliographical note

Funding Information:
✩ Work by the first three authors was supported by the Brain Korea 21 Project, The School of Information Technology, KAIST, in 2005. Work by the fourth author was supported by the Hankuk University of Foreign Studies Research Fund of 2005. Work by the fifth author was supported by the National University of Singapore under grant R-252-000-166-112. * Corresponding author. E-mail addresses: (H.-K. Ahn), (O. Cheong), (C.-D. Park), (C.-S. Shin), (A. Vigneron).


  • 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


Dive into the research topics of 'Maximizing the overlap of two planar convex sets under rigid motions'. Together they form a unique fingerprint.

Cite this