Please use this identifier to cite or link to this item:
|Title:||Maximizing the overlap of two planar convex sets under rigid motions|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 13, 2017
checked on Dec 9, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.