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


Computing Some Distance Functions Between Polygons

, et

We present algorithms for computing some distance functions between two (possibly intersecting) polygons, both in the convex and nonconvex cases. The interest for such distance functions comes from applications in robot vision, pattern recognition and contour fitting. We present a linear sequential algorithm and an optimal EREW-PRAM parallel algorithm for the case when the input polygons are convex, and an essentially quadratic sequential algorithm for the case of arbitrary polygons (possibly with holes).

, 15 pages

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