Translator Disclaimer
9 April 1993 Approximating polygonal curves in two and three dimensions
Proceedings Volume 1832, Vision Geometry; (1993) https://doi.org/10.1117/12.142160
Event: Applications in Optical Science and Engineering, 1992, Boston, MA, United States
Abstract
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.
David Eu and Godfried T. Toussaint "Approximating polygonal curves in two and three dimensions", Proc. SPIE 1832, Vision Geometry, (9 April 1993); https://doi.org/10.1117/12.142160
PROCEEDINGS
14 PAGES SHARE