Helmut Alt, Oswin Aichholzer, and Günter Rote:

Matching shapes with a reference point

  1. 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
  2. International Journal on Computational Geometry and Applications 7 (1997), pp. 349-363, (Zbl 883.68118). doi:10.1142/S0218195997000211


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.

  PostScript file (gzipped)   pdf file (gzipped)
other papers about this subject
Last update: January 9, 2008.