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

关键词： 3D-convex-hull Double extremal point Incremental algorithm

作者: Ruqiong LI Jiahuan ZHANG Huai SHEN

作者单位: School of Information mechanical and Electronic Engineering Shanghai Normal University, Shanghai China

会议类型: 国际会议

会议名称: 2011 IEEE 12th International Conference on Computer-Aided Industrial Design & Conceptual Design(2011年第12届国际计算机辅助工业设计与概念设计学术会议)

会议地点: 重庆

会议语种:英文

页码: 1-4

在线出版日期: 2011-12-01（万方平台首次上网日期，不代表论文的发表时间）