Adaptive Approximation of Curves

"Adaptive Approximation of Curves"

We propose adaptive multiscale refinement algorithms for approximating and encoding curves by polygonal curves. We establish rates of approximation of these algorithms in the Hausdor metric. For example, we show that under the mere assumption that the original curve has finite length then the first of these algorithms gives a rate of convergence O(1/n) where n is the number of vertices of the approximating polygonal curve. Similar results giving second order approximation are proven under weak assumptions on the curvature such as L_p integrability, p > 1. Note that for nonadaptive algorithms, to obtain the same order of approximation would require that the curvature is bounded.