New Serial and Parallel Algorithms for Finding Convex Hull Based on Clusters, Domains and Directions from Single to Multitude

Abstract

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).