Optimal polygonal approximation of digitised curves

Polygonal curve fitting involves approximating a discretised planar curve by a sequence of connected straight-line segments, with a certain error norm. The authors consider the case where the knots of the polygon are a subset of the points of the curve and the error norm is uniform. Several algorithms have been proposed for this problem, but the results are generally not optimal. An optimal polygonal-approximation algorithm is presented which gives the minimum number of sides for a uniform error norm. The algorithm employs the concept of an invalid point, leading to a new condition for terminating a segment. The algorithm is experimentally tested and its advantages demonstrated by comparing with Dunham's (1986) and Sklansky and Gonzalez's (1980) algorithms.