Convex hull calculation approach based on BST
Dmitry Matrokhin, Р. В. Голованов · 2018
The paper describes new algorithm based on binary search tree using, which have average case time complexity O(N*log(H)) where N is the size of the input set of points and H is the number of vertices found to be on the convex hull. The algorithm calculates the approximate center and stores all convex hull points in balanced binary search tree by the angle from it. Implementation of the new algorithm is written in C++ and tested against well-known algorithms. We show that our approach works better on low percentage of points in hull which is common case in convex hull calculation.