  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, usually the local Hausdorff or the local Fr\'echet distance.
Here, local means that, for each line segment of the simplified polyline, only
the distance to the corresponding sub-curve in the original polyline is
measured.
  Melkman and O'Rourke [Computational Morphology '88] introduced a geometric
data structure to solve polyline simplification under the local Hausdorff
distance in $O(n^2 \log n)$ time, and Guibas, Hershberger, Mitchell, and
Snoeyink [Int. J. Comput. Geom. Appl. '93] considered polyline simplification
under the Fr\'echet distance as ordered stabbing and provided an algorithm with
a running time of $O(n^2 \log^2 n)$, but they did not restrict the simplified
polyline to use only vertices of the original polyline.
  We show that their techniques can be adjusted to solve polyline
simplification under the local Fr\'echet distance in $O(n^2 \log n)$ time
instead of $O(n^3)$ when applying the Imai--Iri algorithm. Our algorithm may
serve as a more efficient subroutine for multiple other algorithms. We provide
a simple algorithm description as well as rigorous proofs to substantiate this
theorem. We also investigate the geometric data structure introduced by Melkman
and O'Rourke, which we refer to as wavefront, in more detail and feature some
interesting properties. As a result, we can prove that under the L$_1$ and the
L$_\infty$ norm, the algorithm can be significantly simplified and then only
requires a running time of $O(n^2)$. We also define a natural class of
polylines where our algorithm always achieves this running time also in the
Euclidean norm L$_2$.
