Atallah, M. J.; Ribeiro, C. C.; Lifschitz, S. A linear time algorithm for the computation of some distance functions between convex polygons. (English) Zbl 0770.68109 RAIRO, Rech. Opér. 25, No. 4, 413-424 (1991). The authors modify an algorithm of M. J. Atallah [Inf. Process. Lett. 17, 207-209 (1983; Zbl 0527.68051)], computing the Hausdorff distance between two non-intersecting convex polygons, having respectively \(n_ 1\) and \(n_ 2\) vertices, in the time \(O(n_ 1+n_ 2)\), to obtain one computing the distance defined by P. Cox, H. Maitre, M. Minoux and C. C. Ribeiro [Pattern Recognition Lett. 9, 327-334 (1989)], who used for this purpose a trivial \(O(n_ 1n_ 2)\) algorithm. Next, they generalize the obtained algorithm onto the case where the two polygons may intersect. The resulting one has the time complexity \(O(\max\{n_ 1n_ 2\})\). The algorithms were tested on a PC/AT microcomputer-test timing results are also presented. Reviewer: S.Zabek (Lublin) Cited in 3 Documents MSC: 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 68Q25 Analysis of algorithms and problem complexity 65D18 Numerical aspects of computer graphics, image analysis, and computational geometry Keywords:computational geometry; convex polygons; distance computation; contour fitting; robot vision; algorithms Citations:Zbl 0527.68051 PDFBibTeX XMLCite \textit{M. J. Atallah} et al., RAIRO, Rech. Opér. 25, No. 4, 413--424 (1991; Zbl 0770.68109) Full Text: DOI EuDML