Approximation of an open polygonal curve with mininimal number of circular arcs
Astrid Sturm
Freie Universität Berlin

Abstract: An algorithm for approximating a given open polygonal curve with minimal number of circular arcs is introduced. In computer-aided manufacturing environments the paths of cutting tools are usually described with circular arcs and straight line segments. In the literature techniques for greedy algorithms for approximating a polygonal curve with curves of higher order can be found. Without theoretical bounds the quality of these algorithms are difficult to prove. We present an algorithm which allows us to build a directed graph of all possible arcs and look for the shortest path from the start point to the end point of the polygonal curve. We think we can prove a runtime of O(nēlogēn) for a polygonal curve with n vertices.