Approximation of a closed polygon with a minimum number of circular arcs and line segments

Optimal approximation of closed polygons differs from the case of open polygons in the sense that the location of a starting point must be determined in a suitable way. We present an algorithm which first computes a proper extremal arc as starting point and then approximates the input polygon with a minimum number of circular arcs and line segments. The resulting curve is called Cyclic Minimum Arc Path (CMAP). Our algorithm guarantees the CMAP staying inside a user-specified tolerance. In contrast to the existing approaches, we do not restrict the breakpoints of the arc spline to a predefined set of points but choose them automatically. This has considerable effects on the resulting number of segments.We can handle every type of tolerance zone representing the user-specified tolerance as long it is formed by piecewise restricted analytic curves. In case of polygonal tolerance zones the proposed algorithm takes O(n3)O(n3) time for an original polygonal chain with n   vertices. For generating a solution which has at most one additional segment we present an O(n2)O(n2) algorithm.