Reduced-search dynamic programming for approximation of polygonal curves

Approximation of polygonal curves with minimum error (min-epsilon problem) can be solved by dynamic programming, or by graph-theoretical approach. These methods provide optimal solution but they are slow for a large number of vertices. Faster methods exist but they lack the optimality. We try to bridge the gap between the slow but optimal, and the fast but sub-optimal algorithms by giving a new near-optimal approximation algorithm based on reduced-search dynamic programming. The algorithm can be iterated as many times as further improvement is achieved in the optimization. It is simple, fast, and it has a low space complexity. (C) 2003 Elsevier B.V. All rights reserved.