  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(n^3)$), Global-Fr\'echet (in time $O(k
n^5)$), and Local-Fr\'echet (in time $O(n^3)$).
  Our contribution is as follows.
  - Cubic time for all variants: For Global-Fr\'echet we design an algorithm
running in time $O(n^3)$. 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 $(\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\'echet, and Global-Fr\'echet). Specifically, improving the cubic time
to $O(n^{3-\epsilon} \textrm{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 \ne 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\'echet, and Global-Fr\'echet, by providing new algorithms and
conditional lower bounds.
