Groupe d’études et de recherche en analyse des décisions


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


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

Ce cahier a été révisé en mai 1991