An algorithm for the optimum piecewise linear approximation of digitized curves

A dynamic programming algorithm for piecewise linear approximation of a digitized curve is presented. This approximation yields a global minimization of the total error between the approximating straight-line segments and the original points. Many error measures can be used with this algorithm although a lower computational cost can be achieved if error measures that can be computed incrementally are used. Two incremental formulations of classical error measures, along with the results of a sample experiment, are also presented