---
_id: '3037'
abstract:
- lang: eng
text: For two given simple polygonsP, Q, the problem is to determine a rigid motionI
ofQ giving the best possible match betweenP andQ, i.e. minimizing the Hausdorff
distance betweenP andI(Q). Faster algorithms as the one for the general problem
are obtained for special cases, namely thatI 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 betweenP and an imageI(Q)
ofQ, the distance between the centroids of the edges of the convex hulls ofP andI(Q)
is a constant multiple of the Hausdorff distance betweenP andI(Q). It is also
shown that the Hausdorff distance between two polygons can be determined in timeO(n
logn), wheren is the total number of vertices.
author:
- first_name: Helmut
full_name: Alt, Helmut
last_name: Alt
- first_name: Bernd
full_name: Behrends, Bernd
last_name: Behrends
- first_name: Johannes
full_name: Blömer, Johannes
id: '23'
last_name: Blömer
citation:
ama: Alt H, Behrends B, Blömer J. Approximate matching of polygonal shapes. *Annals
of Mathematics and Artificial Intelligence*. 1995;13(3).
apa: Alt, H., Behrends, B., & Blömer, J. (1995). Approximate matching of polygonal
shapes. *Annals of Mathematics and Artificial Intelligence*, *13*(3).
bibtex: '@article{Alt_Behrends_Blömer_1995, title={Approximate matching of polygonal
shapes}, volume={13}, number={3}, journal={Annals of Mathematics and Artificial
Intelligence}, author={Alt, Helmut and Behrends, Bernd and Blömer, Johannes},
year={1995} }'
chicago: Alt, Helmut, Bernd Behrends, and Johannes Blömer. “Approximate Matching
of Polygonal Shapes.” *Annals of Mathematics and Artificial Intelligence*
13, no. 3 (1995).
ieee: H. Alt, B. Behrends, and J. Blömer, “Approximate matching of polygonal shapes,”
*Annals of Mathematics and Artificial Intelligence*, vol. 13, no. 3, 1995.
mla: Alt, Helmut, et al. “Approximate Matching of Polygonal Shapes.” *Annals of
Mathematics and Artificial Intelligence*, vol. 13, no. 3, 1995.
short: H. Alt, B. Behrends, J. Blömer, Annals of Mathematics and Artificial Intelligence
13 (1995).
date_created: 2018-06-05T08:38:41Z
date_updated: 2019-01-03T13:13:59Z
department:
- _id: '64'
extern: '1'
intvolume: ' 13'
issue: '3'
language:
- iso: eng
publication: Annals of Mathematics and Artificial Intelligence
publication_identifier:
issn:
- 1573-7470
publication_status: published
quality_controlled: '1'
status: public
title: Approximate matching of polygonal shapes
type: journal_article
user_id: '25078'
volume: 13
year: '1995'
...