Journal article
Efficient algorithms for approximating polygonal chains
Discrete & computational geometry, Vol.23(2), pp.273-291
03/01/2000
DOI: 10.1007/PL00009500
Abstract
We consider the problem of approximating a polygonal chain C by another polygonal chain C' whose vertices are constrained to be a subset of the set of vertices of C. The goal is to minimize the number of vertices needed in the approximation C'. Based on a framework introduced by Imai and Iri [25], we define an error criterion for measuring the quality of an approximation. We consider two problems. (1) Given a polygonal chain C and a parameter epsilon greater than or equal to 0, compute an approximation of C, among all approximations whose error is at most epsilon, that has the smallest number of vertices. We present an O(n(4/3+delta))-time algorithm to solve this problem, for any delta > 0; the constant of proportionality in the running time depends on delta. (2) Given a polygonal chain C and an integer k, compute an approximation of C with at most k vertices whose error is the smallest among all approximations with at most k vertices. We present a simple randomized algorithm, with expected running time O (n(4/3+delta)), to solve this problem.
Details
- Title: Subtitle
- Efficient algorithms for approximating polygonal chains
- Creators
- P K Agarwal - Duke UniversityK R Varadarajan - Rutgers, The State University of New Jersey
- Resource Type
- Journal article
- Publication Details
- Discrete & computational geometry, Vol.23(2), pp.273-291
- Publisher
- Springer Nature
- DOI
- 10.1007/PL00009500
- ISSN
- 0179-5376
- eISSN
- 1432-0444
- Number of pages
- 19
- Language
- English
- Date published
- 03/01/2000
- Academic Unit
- Computer Science
- Record Identifier
- 9984259461502771
Metrics
3 Record Views