Polyline simplification has cubic complexity

In the classic polyline simplification problem, given a polygonal curve P con-sisting of n vertices and an error threshold δ ≥ 0, we want to replace P by a subsequence Q of minimal size such that the distance between the polygonal curves P and Q is at most δ. The distance between curves is usually measured using the Hausdorff or continuous Fréchet distance. These distance measures can be applied globally, i.e., to the whole curves P and Q, or locally, i.e., to each simplified subcurve and the line segment that it was replaced with separately (and then taking the maximum). This gives rise to four problem variants: Global-Hausdorff simplification (known to be NP-hard), Local-Hausdorff simplification (can be solved in time O(n³)), Global-Fréchet simplification (can be solved in time O(kn⁵), where k is the size of the optimum simplification), and Local-Fréchet simplification (can be solved in time O(n³)). Our contribution is as follows: • Cubic time for all variants: For Global-Fréchet simplification, we design an algorithm running in time O(n³). This shows that all three problems (Local-Hausdorff, Local-Fréchet, and Global-Fréchet) can be solved in cubic time. All these algorithms work over a general metric space such as (R^d, L_p), but the hidden constant depends on p and (linearly) on d. • Cubic conditional lower bound: We provide evidence that in high dimensions, cubic time is essentially optimal for all three problems (Local-Hausdorff, Local-Fréchet, and Global-Fréchet). Specifically, improving the cubic time to O(n^3−ɛ poly(d)) for polyline simplification over (R^d, L_p) for p = 1 would violate plausible conjectures. We obtain similar results for all p ∈ [1, ∞), p ≠ 2. In total, in high dimensions and over general L_p-norms we resolve the complexity of polyline simplification with respect to Local-Hausdorff, Local-Fréchet, and Global-Fréchet, by a providing new algorithm and conditional lower bounds.