An algorithm for optimal polygonal approximation is presented. Given a
value for the maximal allowed distance between the approximation and
the curve, the algorithm finds an approximation with the minimal numbe
r of vertices. The city-block metric is used to measure the distance b
etween the approximation and the curve. The algorithm worst case compl
exity is O(n(2)), where n is the number of points in the curve. An eff
icient and optimal solution for the case of closed curves where no ini
tial point is given, is also presented.