[{"type":"journal_article","department":[{"_id":"64"}],"intvolume":" 13","title":"Approximate matching of polygonal shapes","issue":"3","user_id":"25078","publication_identifier":{"issn":["1573-7470"]},"year":"1995","_id":"3037","date_created":"2018-06-05T08:38:41Z","language":[{"iso":"eng"}],"abstract":[{"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.","lang":"eng"}],"citation":{"mla":"Alt, Helmut, et al. “Approximate Matching of Polygonal Shapes.” *Annals of Mathematics and Artificial Intelligence*, vol. 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.","chicago":"Alt, Helmut, Bernd Behrends, and Johannes Blömer. “Approximate Matching of Polygonal Shapes.” *Annals of Mathematics and Artificial Intelligence* 13, no. 3 (1995).","short":"H. Alt, B. Behrends, J. Blömer, Annals of Mathematics and Artificial Intelligence 13 (1995).","ama":"Alt H, Behrends B, Blömer J. Approximate matching of polygonal shapes. *Annals of Mathematics and Artificial Intelligence*. 1995;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} }","apa":"Alt, H., Behrends, B., & Blömer, J. (1995). Approximate matching of polygonal shapes. *Annals of Mathematics and Artificial Intelligence*, *13*(3)."},"extern":"1","quality_controlled":"1","status":"public","publication":"Annals of Mathematics and Artificial Intelligence","volume":13,"publication_status":"published","author":[{"full_name":"Alt, Helmut","last_name":"Alt","first_name":"Helmut"},{"full_name":"Behrends, Bernd","first_name":"Bernd","last_name":"Behrends"},{"id":"23","full_name":"Blömer, Johannes","last_name":"Blömer","first_name":"Johannes"}],"date_updated":"2019-01-03T13:13:59Z"}]