COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
- 1 March 1995
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 05 (01n02) , 75-91
- https://doi.org/10.1142/s0218195995000064
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: