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
Source: 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.

SCOPUSTM   
Citations

3
checked on Dec 13, 2017

Page view(s)

65
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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