APPROXIMATION OF POLYGONAL CURVES WITH MINIMUM NUMBER OF LINE SEGMENTS OR MINIMUM ERROR

Abstract

We improve the time complexities for solving the polygonal curve approximation problems formulated by Imai and Iri. The time complexity for approximating any polygonal curve of n vertices with minimum number of line segments can be improved from O(n 2 log n) to O(n 2 ). The time complexity for approximating any polygonal curve with minimum error can also be improved from O(n 2 log 2 n) to O(n 2 log n). We further show that if the curve to be approximated forms part of a convex polygon, the two problems can be solved in O(n) and O(n 2 ) time respectively for both open and closed polygonal curves.