Please use this identifier to cite or link to this item:
Title: Maximizing the overlap of two planar convex sets under rigid motions
Authors: Ahn, H.-K.
Cheong, O.
Park, C.-D.
Shin, C.-S.
Vigneron, A. 
Keywords: Approximation algorithm
Convex shape
Pattern matching
Sublinear algorithm
Issue Date: 2005
Citation: Ahn, H.-K.,Cheong, O.,Park, C.-D.,Shin, C.-S.,Vigneron, A. (2005). Maximizing the overlap of two planar convex sets under rigid motions. Proceedings of the Annual Symposium on Computational Geometry : 356-363. ScholarBank@NUS Repository.
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. Copyright 2005 ACM.
Source Title: Proceedings of the Annual Symposium on Computational Geometry
DOI: 10.1145/1064092.1064146
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Dec 9, 2018

Page view(s)

checked on Dec 8, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.