|
Center for Geometric Computing
Department of Computer Science Johns Hopkins University Baltimore, MD 21218 [barequet|goodrich]@cs.jhu.edu |
Dept. of Computer Science and Engineering
University of Notre Dame Notre Dame, IN 46556 [chen|odaescu]@cse.nd.edu |
In this paper we present efficient algorithms for solving polygonal path approximation problems in three dimensions. Given an n-vertex polygonal curve P in R3, we approximate P by another polygonal curve P' of m vertices in R3, 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 epsilon (called the min-# problem), or to minimize the deviation error epslion between P and P' for a given size m of P' (called the min-epsilon problem). Our techniques enable us to develop efficient near-quadratic-time algorithms for solving the min-# and min-epsilon problems in 3-D.