Helmut Alt, Ulrich Fuchs, Günter Rote, and Gerald Weber:
Matching convex shapes with respect to the symmetric difference
In: Algorithms—ESA '96", Proc. Fourth Annual European Symposium
on Algorithms, Barcelona, September 25–27, 1996. Editors: Josep
María Serna. Lecture Notes in Computer Science 1136, Springer-Verlag,
1996, pp. 320–333.
21 (1998), 89–103. doi:10.1007/PL00009210
We consider the problem of moving one convex figure over another, minimizing
the area of their symmetric difference. We show that if we just let the two
centers of coincide, the resulting symmetric difference is within a factor of
11/3 of the optimum. This leads to efficient approximate matching algorithms
for convex figures.
Last update: August 15, 2017.