Approximating polygonal curves in two and three dimensions

David Eu; Godfried T. Toussaint

doi:10.1117/12.142160

9 April 1993 Approximating polygonal curves in two and three dimensions

David Eu, Godfried T. Toussaint

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 [p₁, p₂, ..., p_n], the polygonal approximation problem considered in this paper calls for determining a new curve P^' equals [p^'₁, p^'₂, ..., 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 [p_B, ..., p_C] in P is such that for all i where B <= i <= C, the approximation error of P_i 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 R^d, 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 R² and with any one of the L₁, L₂ or L_(infinity) distance metrics, we give algorithms to solve the min-# problem in O(n²) time and the min-(epsilon) problem in O(n² log n) time, improving the best known algorithms to date by a factor of log n. When P is a polygonal curve in R³ that is strictly monotone with respect to one of the three axes, we show that if the L₁ and L_INF metrics are used then the min-# problem can be solved in O(n²) time and the min-(epsilon) problem can be solved in O(n³) time. All our algorithms exhibit O(n²) space complexity.

Citation Download Citation

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

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
14 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Tolerancing

Image segmentation

Vision geometry

Data compression

Computer programming

Distance measurement

Radon

Show All Keywords

Keywords/Phrases

Search In:

Publication Years