Matching Convex Shapes With Respect to the Symmetric Difference

Helmut Alt, Ulrich Fuchs, Gerald Weber
Institut für Informatik
Freie Universität Berlin
Takustr. 9, 14195 Berlin
email: [alt,fuchs,weber]@inf.fu-berlin.de

Günter Rote
Institut für Mathematik
Technische Universität Graz
Steyrergasse 30
A-8010 Graz
email: rote@ftug.dnet.tu-graz.ac.at

Report B 96-03
April 1996

This paper deals with questions from convex geometry related to shape matching. In particular, we consider the problem of matching convex figures minimizing the area of the symmetric difference. The main theorem of this paper states, that if we just match the two centers of gravity the resulting symmetric difference is within a factor of 11/3 from the optimal one. This leads to efficient approximate matching algorithms for convex figures.

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-96-03.ps.gz