Matching shapes with A reference point

Oswin Aichholzer*, Helmut Alt, Güter Rote

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)349-363
Number of pages15
JournalInternational Journal of Computational Geometry and Applications
Issue number4
Publication statusPublished - 1997


  • Approximation algorithms
  • Hausdorff distance
  • Pattern matching
  • Selectors
  • Steiner point

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Matching shapes with A reference point'. Together they form a unique fingerprint.

Cite this