A Parallel Dynamic Convex Hull Algorithm Based on the Macro to Micro Model

In this paper, we analyze how humans can solve problems quickly by the process of solving the problem of convex hull. Then we present the M2M (macro to micro) data structure which maintains a finite set of n points in the plane under insertion and deletion of points in amortized O(1) time per operation and O(n) space usage. In addition, as the insert operation of each point is independent, the algorithm has high parallelism. And because the insert operations will not cause the imbalance of the tree structure, the M2M data structure is dynamic. Moreover, it can be shared by all the algorithms based on M2M model which greatly improves the efficiency when a variety of algorithms work simultaneity, such as in image processing and pattern recognition. In all, the M2M model points out a general pattern for designing high parallel algorithms, an efficient strategy for solving multi-operational problems and a new approach for computer to stimulate the thinking pattern of human beings.