Polyline Simplification has Cubic Complexity
Karl Bringmann, Bhaskar Ray Chaudhury · Journal of Computational Geometry (Carleton University) · 2018
$\DeclareMathOperator{\poly}{poly}$In the classic polyline simplification problem, given a polygonal curve~$P$ consisting of $n$ vertices and an error threshold $\delta \geq 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 $\delta$. 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^3)$), Global-Fréchet simplification (can be solved in time $O(k n^5)$, where $k$ is the size of the optimum simplification), and Local-Fr\'{e}chet simplification (can be solved in time $O(n^3)$). Our contribution is as follows: • Cubic time for all variants:\ For Global-Fréchet simplification, we design an algorithm running in time $O(n^3)$. 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 $(\mathbb{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-\epsilon} \poly(d))$ for polyline simplification over $(\mathbb{R}^d,L_p)$ for $p = 1$ would violate plausible conjectures. We obtain similar results for all $p \in [1,\infty), p e 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.