An improved algorithm and implementation for three-dimensional convex hull

被引：1

作者：

Li Ruqiong ^{[1
]}

Zhang Jiahuan ^{[1
]}

Shen Huai ^{[1
]}

Li Zhi ^{[1
]}

机构：

[1] Shanghai Normal Univ, Sch Informat Mech & Elect Engn, Shanghai, Peoples R China

来源：

2013 FIFTH INTERNATIONAL CONFERENCE ON MEASURING TECHNOLOGY AND MECHATRONICS AUTOMATION (ICMTMA 2013) | 2013年

关键词：

3D-convex-hull; Double extremal point; Incremental algorithm;

D O I：

10.1109/ICMTMA.2013.327

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A novel and efficient approach for three-dimensional convex hull was presented in the paper, comparing with the Quick Hull 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 Quick Hull method (the average execution time-consuming reduced by 20%)

引用

页码：198 / 202

页数：5