Translator Disclaimer
9 April 1993 Approximating polygonal curves in two and three dimensions
Author Affiliations +
Proceedings Volume 1832, Vision Geometry; (1993)
Event: Applications in Optical Science and Engineering, 1992, Boston, MA, United States
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.
© (1993) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
David Eu and Godfried T. Toussaint "Approximating polygonal curves in two and three dimensions", Proc. SPIE 1832, Vision Geometry, (9 April 1993);


Binary coding for hyperspectral imagery
Proceedings of SPIE (October 15 2004)
Interactions between number theory and image analysis
Proceedings of SPIE (October 23 2000)
Dual-Mode Hybrid Compressor For Facsimile Images
Proceedings of SPIE (December 28 1979)

Back to Top