Efficiently approximating polygonal paths in three and higher dimensions

Abstract

We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions. Given an n-vertex polygonal curve P in EL', d 2 3, we approximate P by another polygonal curve P' of m 5 n vertices in IR! such that the vertex sequence of P' is an ordered subsequence of the vertices of P. The goal is to either minimize the size m of P' for a given error tolerance E (called the min-# problem), or to minimize the deviation error E between P and P' for a given size m of P' (called the min-.s problem). Our techniques enable us to develop efficient nearquadratic-time algorithms in 3-D and sub-cubictime algorithms in 4-D for solving the mm-# and mine problems. We discuss extensions of our solutions to d-dimensional space, where d > 4.