An improved algorithm and implementation for three-dimensional convex hull

摘要

A novel and efficient approach for threedimensional convex hull was presented in the paper ,comparing with the QuickHull method , the quadratic extremal-point was employed to construct the convex hull in the method, combined with "conflict map" (Conflict-Graph) of this bipartite graph structure to updated the topological relations between the points outside the convex hull and the current convex hull. This algorithm's time complexity is O (nlogr),the experimental results shows that the algorithm is more efficient when compared with the QuickHull method ,the average execution time-consuming reduced by 20%) .