Please use this identifier to cite or link to this item: https://doi.org/10.1145/1064092.1064146
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. https://doi.org/10.1145/1064092.1064146
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
URI: http://scholarbank.nus.edu.sg/handle/10635/40716
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.

Google ScholarTM

Check

Altmetric


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