Back

G-90-23

A linear Time Algorithm for the Computation of Some Distance Functions Between Convex Polygons

and

BibTeX reference

We present in this paper a linear time algorithm for the computation of some distance functions between convex polygons in R2 in the general case where they can intersect. The interest for this problem comes from applications in robot vision, pattern recognition and contour fitting, see Cox, Maitre, Minoux and Ribeiro [1989]. The algorithm is based on previous work of Atallah [1983] for the computation of the Hausdorff distance between disjoint convex polygons. Computational results are presented.

, 15 pages

This cahier was revised in May 1991