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
