Proceedings Article | 9 April 1993
KEYWORDS: Tolerancing, Image segmentation, Vision geometry, Data compression, Distance measurement, Computer programming, Radon, Molybdenum, Binary data, Algorithms
Given a polygonal curve P equals [p1, p2, ..., pn], the polygonal approximation problem considered in this paper calls for determining a new curve P' equals [p'1, p'2, ..., p'm] such that (i) m is significantly smaller than n, (ii) the vertices of P' are a subset of the vertices of P and (iii) any line segment [p'A,p'A+1] of P' that substitutes a chain [pB, ..., pC] in P is such that for all i where B <= i <= C, the approximation error of Pi with respect to [p'A,p'A+1], according to some specified criterion and metric, is less than a predetermined error tolerance. Using the parallel- strip error criterion, we study the following problems for a curve P in Rd, where d >= 2: (1) minimize m for a given error tolerance and (ii) given m, find the curve P' that has the minimum approximation error over all curves that have at most m vertices. These problems are called the min-# and min-(epsilon) problems, respectively. For R2 and with any one of the L1, L2 or L(infinity) distance metrics, we give algorithms to solve the min-# problem in O(n2) time and the min-(epsilon) problem in O(n2 log n) time, improving the best known algorithms to date by a factor of log n. When P is a polygonal curve in R3 that is strictly monotone with respect to one of the three axes, we show that if the L1 and LINF metrics are used then the min-# problem can be solved in O(n2) time and the min-(epsilon) problem can be solved in O(n3) time. All our algorithms exhibit O(n2) space complexity.
