A near-linear time guaranteed algorithm for digital curve simplification under the Fréchet distance

Isabelle Sivignon (1)

1 GIPSA-AGPIG - GIPSA - Architecture, Géométrie, Perception, Images, Gestes

Given a digital curve and a maximum error, we propose an algorithm that computes a simplification of the curve such that the Fréchet distance between the original and the simplified curve is less than the error. The algorithm uses an approximation of the Fréchet distance, but a guarantee over the quality of the simplification is proved. Moreover, even if the theoretical complexity of the algorithm is in O(n log(n)), experiments show a linear behaviour in practice.

Domaines: Traitement des images [eess.IV]

Isabelle Sivignon. A near-linear time guaranteed algorithm for digital curve simplification under the Fréchet distance. DGCI 2011 - 16th IAPR International Conference on Discrete Geometry for Computer Imagery, Apr 2011, Nancy, France. pp.333-345, ⟨10.1007/978-3-642-19867-0_28⟩. ⟨hal-00643520⟩