## Approximate Matching of Polygonal Shapes

```
Helmut Alt, Bernd Behrends, Johannes Blömer
Institut für Informatik
Freie Universität Berlin
e-mail: alt@inf.fu-berlin.de
Report B 93-10
July 93
```
```Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-93-10.ps.gz
```
For two given simple polygons \$P,Q\$ the problem is to determine a rigid motion \$I\$ of \$Q\$ giving the best possible match between \$P\$ and \$Q\$, i.e.\ minimizing the Hausdorff-distance between \$P\$ and \$I(Q)\$. Faster algorithms as the one for the general problem are obtained for special cases, namely that \$I\$ is restricted to translations or even to translations only in one specified direction. It turns out that determining pseudo-optimal solutions, i.e.\ ones that differ from the optimum by just a constant factor can be done much more efficiently than determining optimal solutions. In the most general case the algorithm for the pseudo-optimal solution is based on the surprising fact that for the optimal possible match between \$P\$ and an image \$I(Q)\$ of \$Q\$ the distance between the centroids of the edges of the convex hulls of \$P\$ and \$I(Q)\$ is a constant multiple of the Hausdorff-distance between \$P\$ and \$I(Q)\$. It is also shown that the Hausdorff-distance between two polygons can be determined in time \$O(n\log n)\$, where \$n\$ is the total number of vertices.