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
(
1
/
ε
)
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 that are given in an array or balanced tree, the total running time is
O
(
(
1
/
ε
)
log
n
+
(
1
/
ε
2
)
log
(
1
/
ε
)
)
for rigid motions and
O
(
(
1
/
ε
)
log
n
+
(
1
/
ε
)
log
(
1
/
ε
)
)
for translations.