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 conferencePaperpeer-review

3 Scopus citations

Abstract

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(l/ε) 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, the total running time is O((1/ε) logn+(1/ε2) log(1/ε)) for rigid motions and O((1/ε) log n + (1/ε) log(1/ε)) for translations.

Original languageEnglish (US)
Pages356-363
Number of pages8
DOIs
StatePublished - Dec 1 2005
Event21st Annual Symposium on Computational Geometry, SCG'05 - Pisa, Italy
Duration: Jun 6 2005Jun 8 2005

Other

Other21st Annual Symposium on Computational Geometry, SCG'05
CountryItaly
CityPisa
Period06/6/0506/8/05

Keywords

  • Approximation algorithm
  • Convex shape
  • Pattern matching
  • Sublinear algorithm

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint 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