Polyline Simplification has Cubic Complexity

In the classic polyline simplification problem we want to replace a given polygonal curve P, consisting of n vertices, by a subsequence P' of k vertices from P such that the polygonal curves P and P' are as close as possible. Closeness is usually measured using the Hausdorff or Fr'echet distance. These distance measures can be applied "globally", i.e., to the whole curves P and P', 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 (known to be NP-hard), Local-Hausdorff (in time O(n3)), Global-Fr'echet (in time O(k n5)), and Local-Fr'echet (in time O(n3)). Our contribution is as follows. - Cubic time for all variants: For Global-Fr'echet we design an algorithm running in time O(n3). This shows that all three problems (Local-Hausdorff, Local-Fr'echet, and Global-Fr'echet) can be solved in cubic time. All these algorithms work over a general metric space such as (ℝd,Lp), 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'echet, and Global-Fr'echet). Specifically, improving the cubic time to O(n3-ε textrmpoly(d)) for polyline simplification over (ℝd,Lp) for p = 1 would violate plausible conjectures. We obtain similar results for all p ∈ [1,∞), p ne 2. In total, in high dimensions and over general Lp-norms we resolve the complexity of polyline simplification with respect to Local-Hausdorff, Local-Fr'echet, and Global-Fr'echet, by providing new algorithms and conditional lower bounds.