## Abstract

Given a polygonal curve P = [P_{1}, P_{2} …, P_{n}], the polygonal approximation problem considered calls for determining a new curve P ′ = [P′_{1}, P′_{2}, …, P′_{m}] such that (i) m is significantly smaller than n, (ii) the vertices of P′ are an ordered 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 R^{d}, where d = 2, 3: (i) 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-ε problems, respectively. For R^{2} and with any one of the L_{1}, L_{2}, or L_{∞} distance metrics, we give algorithms to solve the min-# problem in O (n^{2}) time and the min-ε problem in O (n^{2} log n) time, improving the best known algorithms to date by a factor of log n. When P is a polygonal curve in R^{3} that is strictly monotone with respect to one of the three axes, we show that if the L_{1} and L_{∞} metrics are used then the min-# problem can be solved in O(n^{2}) time and the min-ε problem can be solved in O(n^{3}) time. If distances are computed using the L_{2} metric then the min-# and min-ε problems can be solved in O(n^{3}) and O (n^{3} log n) time, respectively. All of our algorithms exhibit O(n^{2}) space complexity. Finally, we show that if it is not essential to minimize m, simple modifications of our algorithms afford a reduction by a factor of n for both time and space.

Original language | English (US) |
---|---|

Pages (from-to) | 231-246 |

Number of pages | 16 |

Journal | Graphical Models and Image Processing |

Volume | 56 |

Issue number | 3 |

DOIs | |

State | Published - May 1994 |

## ASJC Scopus subject areas

- Modeling and Simulation
- Computer Vision and Pattern Recognition
- Geometry and Topology
- Computer Graphics and Computer-Aided Design