×

A linear time algorithm for the computation of some distance functions between convex polygons. (English) Zbl 0770.68109

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)

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

Citations:

Zbl 0527.68051
PDFBibTeX XMLCite
Full Text: DOI EuDML