欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
对文献（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.
同期刊论文项目
同项目期刊论文
An efficient joint implementation of three stages for fast computation of color space conversation i
期刊信息
位置：