Share Email Print

Proceedings Paper

Approximating polygonal curves in two and three dimensions
Author(s): David Eu; Godfried T. Toussaint
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 9 April 1993
PDF: 14 pages
Proc. SPIE 1832, Vision Geometry, (9 April 1993); doi: 10.1117/12.142160
Show Author Affiliations
David Eu, McGill Univ. (Canada)
Godfried T. Toussaint, McGill Univ. (Canada)

Published in SPIE Proceedings Vol. 1832:
Vision Geometry
Robert A. Melter; Angela Y. Wu, Editor(s)

© SPIE. Terms of Use
Back to Top