Developed Algorithm for Making Up Convex Hull Based on Binary Tree

摘要

In computer vision, convex hulls are used for pattern recognition and other image analysis using special points. This paper suggests the developed algorithm for making up a convex hull based on a binary tree. The main idea of the algorithm, proposed in this paper, is very similar to the underlying principle incremental algorithm. The new algorithm quite quickly exceeds the running time of the Graham algorithm with a large number of points in the convex hull. This is due to the best complexity of the algorithm. The Graham's algorithm has O(nlogn) complexity when the new algorithm has O(nlogh) average complexity.