A Parallel Dynamic Convex Hull Algorithm based on M2M model

In this paper, we introduce a new parallel convex hull algorithm based on dynamic M2M data structure whose operation such as inserting or deleting costs O(1) time. In practice, this algorithm is faster than the classical convex hull algorithms such as Grahan scan, quick hull and Jarvis march. As with other M2M algorithm, this algorithm share an identical preprocessing which takes the majority of the costing time of the entire algorithm. Such characteristic is very helpful in many applications where a large number of operations need to be executed to the same data set.