On approximating polygonal curves in two and three dimensions

Given a polygonal curve P = [p₁, p₂, · · ·, p_n], the polygonal approximation problem considered in this paper calls for determining a new curve P' = [p₁, p₂> · · ·, p_m] such that (i) m is significantly smaller than n, (ii) the vertices of P are a subset of the vertices of P and (iii) any line segment [p_A, p_A+1] of P' that substitutes a chain [p_B,..., p_C] in P is such that for all i where B ≤ i ≤ C, the approximation error of p_i 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: (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 R2 and with any one of the L₁, L₂ or L_∞ distance metrics, we give algorithms to solve the min-# problem in 0(n²) time and the min-∈ problem in 0(n² log n) time, improving the best known algorithms to date by a factor of log n. When P is a polygonal curve in R³ that is strictly monotone with respect to one of the three axes, we show that if the L₁ and L_∞ metrics are used then the min-# problem can be solved in O(n²) time and the min-∈ problem can be solved in O(n³) time. If distances are computed using the L₂ metric then the min-# and min-∈ problems can be solved in O(n³) and O(n³ log n) time respectively. All our algorithms exhibit O(n²) space complexity.