For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The Cone Intersection Method for Min-# Polygonal Approximation in R2
Kento MIYAOKU Koichi HARADA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1996/04/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Image Processing,Computer Graphics and Pattern Recognition
polygonal approximation, min-# problem, cone intersection method, parallel-strip error criterion,
Full Text: PDF>>
We propose a new algorithm for minimizing the number of vertices of an approximate curve by keeping the error within a given bound (min-# problem) with the parallel-strip error criterion. The best existing algorithm which solves this problem has O (n2 log n) time complexity. Our algorithm which uses the Cone Intersection Method does not have an improved time complexity, but does have a high efficiency. In particular, for practical data such as those which represent the boundaries or the skeletons of an object, the new algorithm can solve the min-# problem in nearly O(n2) time.