A Parallel Dynamic Convex Hull Algorithm based on M2M model

作者：Zhang YingPeng^*; Chen Qiong; Zhang ZhiZhuo; Zhou ZhiMing; Luo ShengZhou

来源：Information-An International Interdisciplinary Journal, 2008, 11(5): 587-595.

• Convex Hull
• M2M

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.

• 出版日期2008-9
• 单位华南理工大学