Using a Linear Data Structure to maintain Dynamic Convex Hull in two Dimensions

Abstract

Finding convex hull of a set of data points is an interesting problem in Computer Science and Mathematics. This paper concentrates on the use of linear data structure to solve dynamic convex hull problem. In this study, we propose a convex hull algorithm that dynamically computes convex hull of a data set where new data points are inserted randomly without deleting existing ones. Given the initial convex hull, the algorithm dynamically maintains the relevant convex hull according to the random appearance of data points. The proposed algorithm is useful in situations where dynamic construction of a new convex hull is required as a result of randomly inserting new set of data points to a large number of exiting data points with an already computed convex hull. The use of static algorithms, in such situations, requires constructing the convex hull from scratch every time a new data point is inserted and involves unnecessary computational cost. The proposed algorithm is tested against data sets having large number of randomly generated data points and gave satisfactory results.