A simple and efficient incremental convex hull algorithm in 3D space

Abstract

The convex hull of a set S of points can be defined as the smallest convex set containing all the points in S. The smallest convex set can be identified as the smallest convex polyhedron in three dimensions. There are four ex isting 3D convex hull algorithms: Naïve, Gift Wrapping, Divide & Conquer, and Incremental with O (n 3 ), O (nF), O (n log n), and O (n 2 ) time complexities respectively where n is the number of points and F is the number of facets of the convex hull. The firs t three algorithms require the entire set of points at the beginning to process. The incremental algorithm can maintain the convex hull covering the points appearing one by one in space. The existing incremental algorithm is very complicated due to the use of advanced data structures for the implementation. The objective of this work is to propose a new simpler algorithm. The convex hull is represented by a set of triangular facets. If the new point appears inside the existing convex hull then the point is ignored. If the new point appears outside the existing convex hull then some set of facets should be removed from the current convex hull and a new set of facets should be added. If there are n points currently in the space, then there are kn facets in the convex hull where k << n in the worst case. It takes O (kn) = O (n) time to test whether the new point is outside each facet. In the worst case, the new point is outside for ( kn 1) facets. Therefore, removing duplicate facets cost O [{3(kn 1)} 2 ] = O n 2 ) time. Thus the proposed algorithm has O (n) + O (n 2 ) = O (n 2 ) time complexity in the worst