SPACE-EFFICIENT ALGORITHMS FOR APPROXIMATING POLYGONAL CURVES IN TWO-DIMENSIONAL SPACE
Danny Z. Chen, Ovidiu Daescu · International Journal of Computational Geometry & Applications · 2003
Given an n-vertex polygonal curve P = [p1, p2, …, pn] in the 2-dimensional space R2, we consider the problem of approximating P by finding another polygonal curve [Formula: see text] such that the vertex sequence of P′ is an ordered subsequence of the vertices along P. The goal is to either minimize the size m of P′ for a given error tolerance ∊ (called the min-# problem), or minimize the deviation error ∊ between P and P′ for a given size m of P′ (called the min-∊ problem). We present useful techniques and develop efficient algorithms for solving the 2-D min-# and min-∊ problems under two commonly-used error criteria for curve approximations. Our algorithms improve substantially the space bounds of the previously best known results on the same problems while maintain the same time bounds as those of the best known algorithms. We further show that our 2-D techniques can be used to improve the time and space bounds for a special case of the 3-D min-# and min-∊ problems.