Efficient algorithms for 3-D polygonal approximation based on LISE criterion

摘要

Given a polygonal curve P in three-dimensional (3-D) space, the polygonal approximation (PA) problem in this research is to find a polygon P′ to approximate P either with the minimal polygonal segments under a given error or, conversely, with the minimal error under a specified number of segments allowable. The former PA problem is called the PA-# problem; the latter PA problem is called the PA-ε problem. Given a 3-D P with n nodes, under the local integral square error criterion, this paper first presents an O(n2)-time algorithm for solving the PA-# problem using O(n) space. Then we present an O(n2logn)-time algorithm for solving the PA-ε using O(n2) space. Finally, a sampling technique is employed to reduce the memory requirement from O(n2) to O(n). Some experiments are carried out to confirm the theoretical analysis.