Maximizing the overlap of two planar convex sets under rigid motions

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
Keywords

POLYGONS; APPROXIMATION; AREA

Citation

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

ISSN
0925-7721
DOI
10.1016/j.comgeo.2006.01.005
URI
http://hdl.handle.net/10203/301
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
acpsv-motpc.pdf(247.3 kB)Download
  • Hit : 446
  • Download : 268
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 11 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0