A fast convex hull algorithm with maximum inscribed circle affine transformation

This paper presents a fast convex hull algorithm for a large point set. The algorithm imitates the procedure of human visual attention derived in a psychological experiment. The merit of human visual attention is to neglect most inner points directly. The proposed algorithm achieves a significant sa...

Full description

Saved in:
Bibliographic Details
Published in:Neurocomputing (Amsterdam) 2012-02, Vol.77 (1), p.212-221
Main Authors: Liu, Runzong, Fang, Bin, Tang, Yuan Yan, Wen, Jing, Qian, Jiye
Format: Article
Language:English
Subjects:
Affine transformation
Affine transformations
Algorithms
Computation
Computational geometry
Convex hull
Hulls
Hulls (structures)
Human
Point pattern
Shape analysis
Visual
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents a fast convex hull algorithm for a large point set. The algorithm imitates the procedure of human visual attention derived in a psychological experiment. The merit of human visual attention is to neglect most inner points directly. The proposed algorithm achieves a significant saving in time and space in comparison with the two best convex hull algorithms mentioned in a latest review proposed by Chadnov and Skvortsov in 2004. Furthermore, we propose to use an affine transformation to solve the narrow shape problem for computing the convex hull faster.
ISSN:0925-2312
1872-8286
DOI:10.1016/j.neucom.2011.09.011