Polygonal Approximations of a Curve — Formulations and Algorithms

A general framework for polygonal approximation problems in various situations is given, and solution algorithms are discussed. The problems are classified according to three criteria: (1) whether the curve is the graph of a piecewise linear function y=f(x) of the independent variable x, or it is a general polygonal curve in the plane, (2) which error criterion is adopted (for a piecewise linear function, we consider only one criterion), (3) whether the objective is to minimize the number of vertices of the approximate curve when an error bound is given, or to minimize the approximation error when the number of vertices of the approximate curve is specified. The problems are first formulated in terms of graph theory, and then computationally efficient algorithms are constructed by taking advantage of fundamental algorithms for convex hulls in computational geometry.