Computing some distance functions between polygons

摘要

We present algorithms for computing some distance functions between two (possibly intersecting) polygons, in both the convex and nonconvex cases. The interest for such distance functions comes from applications in robot vision, pattern recognition and contour fitting. We present 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).