Fréchet Similarity of Closed Polygonal Curves

Abstract

The article analyzes similarity of closed polygonal curves with respect to the Fréchet metric, which is stronger than the well-known Hausdorff metric and therefore is more appropriate in some applications. An algorithm is described that determines whether the Fréchet distance between two closed polygonal curves with [Formula: see text] and [Formula: see text] vertices is less than a given number [Formula: see text]. The algorithm takes [Formula: see text] time whereas the previously known algorithms take [Formula: see text] time.