[IPOL announce] new article: A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification Under the Fréchet Distance

[announcements about the IPOL journal]

A new article is available in IPOL: http://www.ipol.im/pub/art/2014/70/

Isabelle Sivignon,
A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification 
Under the Fréchet Distance,
Image Processing On Line, 4 (2014), pp. 116–127. 
http://dx.doi.org/10.5201/ipol.2014.70

Abstract
In this paper, we propose an algorithm that, from a maximum error and a 
digital curve (4- or 8-connected), computes a simplification of the 
curve (a polygonal curve) such that the Fréchet distance between the 
original and the simplified curve is less than the error. The Fréchet 
distance is known to nicely measure the similarity between two curves. 
The algorithm we propose 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.