CIM Algorithm for Approximating Three-Dimensional Polygonal Curves

The polygonal approximation problem is a primary problem in computergraphics, pattern recognition, CAD/CAM, etc. In R^2, the coneintersection method (CIM) is one of the most efficient algorithms forapproximating polygonal curves. With CIM Eu and Toussaint, by imposingan additional constraint and changing the given error criteria, resolvethe three-dimensional weighted minimum number polygonal approximationproblem with the parallel-strip error criterion (PS-WMN) under L_2norm. In this paper, without any additional constraint and change of theerror criteria, a CIM solution to the same problem with the line segmenterror criterion (LS-WMN) is presented,which is more frequently encountered than the PS-WMN is. Its timecomplexity is O(n^3), and the space complexity is O(n^2).An approximation algorithm is also presented, which takes O(n^2) timeand O(n) space. Results of some examples are given to illustratethe efficiency of these algorithms.