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-epsilon problem. Given a 3-D P with n nodes, under the local integral square error criterion, this paper first presents an O(n(2))-time algorithm for solving the PA-# problem using O(n) space. Then we present an O(n(2) log n)-time algorithm for solving the PA-epsilon using O(n(2)) space. Finally, a sampling technique is employed to reduce the memory requirement from O(n(2)) to O(n). Some experiments are carried out to confirm the theoretical analysis. (C) 2002 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.

[发布日期] 2002-11-01

[关键词] algorithms;dynamic programming;integral square error criterion;3-D polygonal approximation;sampling technique;shortest path