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

Optimal Expected-Time Algorithm for Delaunay Triangulation of Uniform Sites

作　　者：汪嘉业[1,2] 杨承磊[3,4] 张彩明[1,3,2] 吕琳[3,4] 

机构地区：[1]山东财经大学计算机科学与技术学院,济南250014 [2]山东省数字媒体技术重点实验室,济南250014 [3]山东大学计算机科学与技术学院,济南250101 [4]山东省软件工程重点实验室,济南250101

出　　处：《计算机辅助设计与图形学学报》2011年第12期1949-1958,共10页Journal of Computer-Aided Design & Computer Graphics

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

摘　　要：对文献(Dwyer R A.Higher-dimensional Voronoi diagrams in linear expected time.Discrete&ComputationalGeometry,1991,6(4):342-367)给出的对d≥2维空间站点集合构造Delaunay超三角形算法做了改进,提高了其计算效率,并把站点的分布从限于单位球体扩展成d≥2维空间中任意凸的超多面体.证明了如果站点是独立地从一致分布在凸的超多面体的点集中取出,在线性期望时间内可对站点集实现Delaunay三角化.该证明方法比较直观.虽然这类算法对输入点集有一致分布的要求,但在很多实际应用情况下这种要求常是被满足的,此时使用这类算法便可体现文中算法快速和易于实现的优点.This paper presents an algorithm that improves the results in reference（Dwyer R A.Higher-dimensional Voronoi diagrams in linear expected time.Discrete Computational Geometry,1991,6（4）： 342-367）.The improvements are improving the efficiency of the algorithm,extending the region of the sites distributed from a unit sphere to any convex polyhedron.The main results are as following.If the sites are chosen independently from a uniform distribution on a convex d≥2 dimension polyhedron,the modified algorithm can create its Delaunay triangulation in linear time.Although this kind of algorithm requires that sites are drawn independently from a uniform distribution,this requirement is often satisfied by many applications,in which the advantage of simplicity and efficiency of the algorithm can be expressed very well.

关 键 词：DELAUNAY三角化 VORONOI图 超多面体 最佳期望时间 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]