COMPUTING THE FRECHET DISTANCE BETWEEN 2 POLYGONAL CURVES

As a measure for the resemblance of curves in arbitrary dimensions we consider the so-called Frechet-distance, which is compatible with parametrizations of the curves. For polygonal chains P and Q consisting of p and q edges an algorithm of runtime O(pq log(pq)) measuring the Frechet-distance between P and Q is developed. Then some important variants are considered, namely the Frechet-distance for closed curves, the nonmonotone Frechet-distance and a distance function derived from the Frechet-distance measuring whether P resembles some part of the curve Q.