Matching Shapes with a Reference Point
Helmut Alt
Institut für Informatik
Freie Universität Berlin
email: alt@inf.fu-berlin.de
(joint work with Oswin Aichholzer and Günter Rote)
Report B 94-18
October 1994
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-94-18.ps.gz
Matching Shapes with a Reference Point
For two given point sets, we present a very simple
(almost trivial) algorithm to translate one set so that the Hausdorff
distance between the two sets is not larger than a constant factor times
the minimum Hausdorff distance which can be achieved in this way. The
algorithm just matches the so-called Steiner points of the two sets.
The focus of our paper is the general study of reference points (like the
Steiner point) and their properties with respect to shape matching.
For more general transformations than just translations, our method eliminates
several degrees of freedom from the problem and thus yields good matchings
with improved time bounds.