The Cone Intersection Method for Min-# Polygonal Approximation in R2

Kento MIYAOKU  Koichi HARADA  

IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.4   pp.343-348
Publication Date: 1996/04/25
Online ISSN: 
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>>
Buy this Article

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.