Improvement of Perez and Vidal algorithm for the decomposition of digitized curves into line segments

Perez and Vidal proposed (1994) an optimal algorithm for the decomposition of digitized curves into line segments. The number of segments is fixed a priori, and the error criterion is the sum of the square Euclidean distance from each point of the contour to its orthogonal projection onto the corresponding line segment. The complexity of Perez and Vidal algorithm is O(n².m) where n is the number of points and m is the number of segments. We propose improvements of the algorithm to reduce the complexity, using the A* algorithm. The optimality of the algorithm is preserved and its complexity is lower. Some comparative results are presented, showing that our method is systematically faster, in particular for a large number of segments