Efficiently Approximating Polygonal Paths in Three and Higher Dimensions

We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions. Given an n -vertex polygonal curve P in \R ^d , d \geq 3 , we approximate P by another poly- gonal curve P' of m ≤ n vertices in \R ^d such that the vertex sequence of P' is an ordered subsequence of the vertices of P . The goal is either to minimize the size m of P' for a given error tolerance \eps (called the min-\# problem), or to minimize the deviation error \eps between P and P' for a given size m of P' (called the min- \eps problem). Our techniques enable us to develop efficient near-quadratic-time algorithms in three dimensions and subcubic-time algorithms in four dimensions for solving the min-\# and min-\eps problems. We discuss extensions of our solutions to d -dimensional space, where d > 4 , and for the L ₁ and L _∈ fty metrics. Received January 10, 1999; revised November 8, 2000.