对文献(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三角化.该证明方法比较直观.虽然这类算法对输入点集有一致分布的要求,但在很多实际应用情况下这种要求常是被满足的,此时使用这类算法便可体现文中算法快速和易于实现的优点.
Optimal Expected-Time Algorithm for Delaunay Triangulation of Uniform Sites
Wang Jiaye1,3), Yang Chenglei2,4)*, Zhang Caiming1,2,3), and Lu Lin2,4)
1)(School of Computer Science and Technology, Shandong University of Finance and Economics, Ji’nan 250014) 2)(School of Computer Science and Technology, Shandong University, Ji’nan 250101) 3)(Shandong Provincial Key Laboratory of Digital Media Technology, Ji’nan 250014) 4)(Shandong Provincial Key Laboratory of Software Engineering, Ji’nan 250101)
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 triangulation; Voronoi diagram; hyper polyhedron; expected optimization time