Polyline Simplification under the Local Fréchet Distance has Subcubic Complexity in 2D
share
Given a polyline on n vertices, the polyline simplification problem asks for a minimum size subsequence of these vertices defining a new polyline whose distance to the original polyline is at most a given threshold under some distance measure. In this paper, we improve the long-standing running time bound for the simplification of polylines under the local Fréchet distance. The best algorithm known so far is by Imai and Iri and has a cubic running time in n. We present an algorithm with a running time of O(n^2) under the L_1 and L_∞ norm, and O(n^2 log n) under L_p ∈ (1,∞) (including the Euclidean norm L_2). Our approach is based on the ideas of Chan and Chin, who showed that under the local Hausdorff distance, the Imai-Iri algorithm can be improved to run in quadratic time for L_1, L_2, and L_∞. However, the Hausdorff distance does not take the order of the points along the polyline into account. The Fréchet distance, which is sensitive to the course of the polylines, is hence often deemed the superior distance measure for polyline similarity but it also more intricate to compute. So far, the significantly faster simplification algorithms for the Hausdorff distance made them preferable for practical application. But our new algorithm for simplification under the Fréchet distance matches the running time bounds for the Hausdorff distance up to logarithmic factors and thus allows the usage of this more suitable distance measure.
READ FULL TEXT