An efficient planar incremental convex hull algorithm to find the edges of the boundary polygon of the convex hull of a set of points

Abstract

The definition of the convex hull of a set of points is the smallest convex set containing all the points. Many algorithms have been proposed with the worst case time complexity is equal to O (n log n). It has been proved that the lower bound of time complexity for construction of the convex hull is O (n log n). However, these algorithms are static and require all points at the start. Suppose that points reach sequentially one after one and the convex hull needs to be maintained at each insertion of a point. The convex hull should be constructed from the scratch to handle each point insertion if a static convex hull algorithm was used. This process consumes O (n log n) time and therefore it is inefficient. An incremental convex hull algorithm can maintain the convex hull at each insertion performing a trivial modification to the existing convex hull without constructing the convex hull from the scratch. The optimal time complexity for insertion of a point in existing incremental convex hull algorithms is O (n). A new incremental convex hull algorithm with O (h2) time complexity is proposed in this paper. Note that h represents the number of vertices of the convex hull. A set of line segments is used to represent the convex hull. Some of the existing line segments may be deactivated instead of deleting upon the successive growth of the convex hull. Thus, the computational cost is reduced. The proposed algorithm is faster than the existing algorithms when h < SQRT (n) and the concept can be extended to three dimensions.

Keywords

• convex hull, algorithms, computational geometry, data structures, computational complexity