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.

- Publisher
- ELSEVIER SCIENCE BV

- Issue Date
- 2007-05

- Language
- ENG

- Article Type
- Article; Proceedings Paper

- Keywords
POLYGONS; APPROXIMATION; AREA

- Citation
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.37, no.1, pp.3 - 15

- ISSN
- 0925-7721

- Appears in Collection
- CS-Journal Papers(저널논문)

- Files in This Item
- acpsv-motpc.pdf
*(247.3 kB)*Download

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