Helmut Alt, Oswin Aichholzer, and Günter Rote:
Matching shapes with a reference point
- Extended abstract in: Proceedings of the
Tenth Annual Symposium on Computational
Geometry, Stony Brook, New York, June 6-8, 1994. Association
for Computing Machinery, 1994, pp. 85-92. doi:10.1145/177424.177555
- International Journal on Computational Geometry and
Applications
7 (1997), pp. 349-363, (Zbl 883.68118). doi:10.1142/S0218195997000211
Abstract
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.
Last update: January 9, 2008.