MAXIMIZING THE OVERLAP OF TWO PLANAR CONVEX SETS UNDER RIGID MOTIONS
SCIE
SCOPUS
- Title
- MAXIMIZING THE OVERLAP OF TWO PLANAR CONVEX SETS UNDER RIGID MOTIONS
- Authors
- Ahn, HK; Cheong, O; Park, CD; Shin, CS; Vigneron, A
- Date Issued
- 2007-05
- Publisher
- ELSEVIER SCIENCE BV
- 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 epsilon > 0, we compute a rigid motion such that the area of overlap is at least 1-epsilon times the maximum possible overlap. Our algorithm uses O(1/epsilon) extreme point and line intersection queries on P and Q, plus O((1/epsilon(2)) log(1/epsilon)) running time. If only translations are allowed, the extra running time reduces to O((1/epsilon) log(1/epsilon)). If P and Q are convex polygons with n vertices in total that are given in an array or balanced tree, the total running time is O((1/epsilon) log n + (1/epsilon(2)) log(1/epsilon)) for rigid motions and O((1/epsilon) log n + (1/epsilon) log(1/epsilon)) for translations. (c) 2006 Elsevier B.V. All rights reserved.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/28545
- DOI
- 10.1016/j.comgeo.2006.01.005
- ISSN
- 0925-7721
- Article Type
- Article
- Citation
- COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, vol. 37, no. 1, page. 3 - 15, 2007-05
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.