Helmut Alt, Ulrich Fuchs, Günter Rote, and Gerald Weber:

Matching convex shapes with respect to the symmetric difference

  1. In: Algorithms—ESA '96", Proc. Fourth Annual European Symposium on Algorithms, Barcelona, September 25–27, 1996. Editors: Josep Díaz and María Serna. Lecture Notes in Computer Science 1136, Springer-Verlag, 1996, pp. 320–333. doi:10.1007/3-540-61680-2_65
  2. Algorithmica 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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)   free PDF view@Springer
other papers about this subject
Last update: August 15, 2017.