TY - CONF
T1 - Maximizing the overlap of two planar convex sets under rigid motions
AU - Ahn, Hee Kap
AU - Cheong, Otfried
AU - Park, Chong Dae
AU - Shin, Chan Su
AU - Vigneron, Antoine
N1 - 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: [email protected] (H.-K. Ahn), [email protected] (O. Cheong), [email protected] (C.-D. Park), [email protected] (C.-S. Shin), [email protected] (A. Vigneron).
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
KW - Approximation algorithm
KW - Convex shape
KW - Pattern matching
KW - Sublinear algorithm
UR - http://www.scopus.com/inward/record.url?scp=33244493774&partnerID=8YFLogxK
U2 - 10.1145/1064092.1064146
DO - 10.1145/1064092.1064146
M3 - Paper
AN - SCOPUS:33244493774
SP - 356
EP - 363
T2 - 21st Annual Symposium on Computational Geometry, SCG'05
Y2 - 6 June 2005 through 8 June 2005
ER -