Polygonal Curve Simplification

Let $P=(p_1,\ldots,p_n)$ be a polygonal curve, let $\varepsilon>0$, and fix the approximation criterion specified by the input. Among subsequences containing $p_1$ and $p_n$, find one with the minimum number of vertices whose induced curve is within error $\varepsilon$ of $P$. Determine whether an optimal simplification can be computed in near-linear time.