# MPI-I-91-110

## Approximate decision algorithms for point set congruence

### Heffernan, Paul J. and Schirra, Stefan

**MPI-I-91-110**. August** **1991, 25 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 14040 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-110

**BibTeX**
`@TECHREPORT{``HeffernanSchirra91``,`

` 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},`

`}`