Efficiently approximating polygonal paths in three and higher dimensions
Gill Barequet, Michael T. Goodrich, D. Z. Chen, Ovidiu Daescu, Jack Scott Snoeyink · 1998
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-.sproblem).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.