Portal de Periódicos da CAPES

COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES

1995; World Scientific; Volume: 05; Issue: 01n02 Linguagem: Inglês

10.1142/s0218195995000064

1793-6357

Helmut Alt, Michael Godau,

Computational Geometry and Mesh Generation

As a measure for the resemblance of curves in arbitrary dimensions we consider the so-called Fréchet-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 Fréchet-distance between P and Q is developed. Then some important variants are considered, namely the Fréchet-distance for closed curves, the nonmonotone Fréchet-distance and a distance function derived from the Fréchet-distance measuring whether P resembles some part of the curve Q.