We present efficient algorithms for solving polygonal‐path approximation problems in three and higher dimensions. Given an n ‐vertex polygonal curve P in d , d \geq 3 , we approximate P by another poly‐ gonal curve P' of m ≤ n vertices in 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 1 and L ∈ fty metrics.
