New Serial and Parallel Algorithms for Finding Convex Hull Based on Clusters, Domains and Directions from Single to Multitude - Zhou Qihai (Journal of Algorithms & Computational Technology, 2009)
An Isomorphic Fundamental Theorem of the Convex Hull Construction is given and proved. A representative serial algorithm convex hull with half-dividing and recurrence is commented as compared example. A more efficient new serial algorithm to find a convex hull based on a dynamical maximum base line pitch is given; its general characters are: 1) find out the outside-most points as the initial apexes, 2) divide the original distributed domain of a given 2D point set into four sub-domain at most, 3) construct a current apex with a maximum pitch to its base line in every sub-domain. Another new improved serial convex algorithm based on a minimum lever half line pitch coiling with 4-domains and 4-derections in all sub-domains is advanced; its isomorphic new characteristics are: 1) take a new pattern of 1-clusters, 4-domains and 4-directions, 2) construct a current apex with a minimum pitch from its lever half line in every sub-domain, 3) the computational time for finding a current apex is less. Further, a more efficient new parallel algorithm for finding convex hull based on 2-clusters, 2-domains and 4-directions is created; its isomorphic new characteristics are: 1) take pattern of 2-clusters, 2-domains and 4-directions, 2) have great isomorphic new potentialities to construct a better, newer and more efficient parallel algorithm for finding convex hull with m-Clusters, n-Domains and p-Directions (m > 2, n > 2, p > 2).