基于EMST的平面点集Delaunay三角剖分

摘要：

提出一种基于欧几里德最小支撑树(EMST)的平面点集Delaunay三角剖分算法.该算法使用线性时间的随机算法求出平面点集的EMST,逐次加入一边构成三角网络,按照最小角最大化的三角化准则,通过局部变换得到平面点集的Delaunay三角剖分.采用的随机化算法有效节省了寻找EMST的计算时间,提高了整个算法的效率.

关键词： 欧几里德最小支撑树 Delaunay三角剖分 随机算法 平面点集

作者: 余楚才 吴荣泉 许延武

作者单位: 华东计算技术研究所,上海,200233

会议类型: 国内会议

会议名称: 华东计算技术研究所建所50周年庆学术交流会

会议地点: 上海

会议语种:中文

页码: 77-79

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