Efficient algorithms for approximating polygonal chains

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.