MPI-INF/SWS Research Reports 1991-2021

1. Author,Editor - 3. with BibTeX cite keys


Approximate decision algorithms for point set congruence

Heffernan, Paul J. and Schirra, Stefan

August 1991, 25 pages.

Status: available - back from printing

This paper considers the computer vision problem of testing whether two equal cardinality point sets $A$ and $B$ in the plane are $\varepsilon$-congruent. We say that $A$ and $B$ are $\varepsilon$-congruent if there exists an isometry $I$ and bijection $\ell : A \rightarrow B$ such that $dist(\ell(a),I(a)) \leq \varepsilon$, for all $a \in A$. Since known methods for this problem are expensive, we develop approximate decision algorithms that are considerably faster than the known decision algorithms, and have bounds on their imprecision. Our approach reduces the problem to that of computing maximum flows on a series of graphs with integral capacities.

  • MPI-I-91-110.pdf
  • Attachement: MPI-I-91-110.pdf (14040 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Heffernan, Paul J. and Schirra, Stefan},
  TITLE = {Approximate decision algorithms for point set congruence},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-91-110},
  MONTH = {August},
  YEAR = {1991},
  ISSN = {0946-011X},