Efficient Approximation of Polygonal Curves

Danny Z. Chen, University of Notre Dame

Curve approximation problems appear in many application areas, such as image processing, computer graphics, cartography, and data compression. In this talk, we present several geometric techniques and observations for solving polygonal curve approximation problems. Given an \(n\)-vertex polygonal curve \(P = [p_1, p_2, \ldots, p_n]\) in space \(R^d\) (\(d = 3\) or \(d = 2\)), we consider the problem of approximating \(P\) by finding another polygonal curve \(P’ = [p’_1, p’_2, \ldots, p’_m]\) of \(m\) vertices in \(R^d\) 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 \(\epsilon\), or minimize the deviation error \(\epsilon\) between \(P\) and \(P’\) for a given size \(m\) of \(P’\). We develop a number of efficient algorithms for solving 3-D and 2-D polygonal curve approximation problems under two commonly-used error criteria. Our algorithms improve substantially the time and/or space bounds of the previously best known results on the same problems.