一致分布点集Delaunay三角化最佳期望时间算法

摘要：

对文献(Dwyer R A.Higher-dimensional Voronoi diagrams in linear expected time.Discrete&Computational Geometry,1991,6(4):342-367)给出的对d≥2维空间站点集合构造Delaunay超三角形算法做了改进,提高了其计算效率,并把站点的分布从限于单位球体扩展成d≥2维空间中任意凸的超多面体.证明了如果站点是独立地从一致分布在凸的超多面体的点集中取出,在线性期望时间内可对站点集实现Delaunay三角化.该证明方法比较直观.虽然这类算法对输入点集有一致分布的要求,但在很多实际应用情况下这种要求常是被满足的,此时使用这类算法便可体现文中算法快速和易于实现的优点.

关键词：Delaunay三角化、Voronoi图、超多面体、最佳期望时间

所属期刊栏目：23

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金60933008,60573181,61070093;山东省优秀中青年科学家基金BS2009DX026;山东大学自主创新基金2010HW010

在线出版日期：2012-03-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1949-1958