投审稿平台


投稿指南
下载专区
地  址:北京市海淀区中关村科学院
南路6号中国科学院计算所342号 [地图]
《计算机辅助设计与图形学学报》编辑部
邮政编码:100190
电  话:010-62562491
          010-62600342
订阅信息
ISSN      1003-9775
CN        11-2925/TP
邮发代号:82-456
单    价:80.00元
全年订价:960.00元
在线期刊

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

汪嘉业1,3), 杨承磊2,4)*, 张彩明1,2,3), 吕 琳2,4)
1)(山东财经大学计算机科学与技术学院 济南 250014) 2)(山东大学计算机科学与技术学院 济南 250101) 3)(山东省数字媒体技术重点实验室 济南 250014) 4)(山东省软件工程重点实验室 济南 250101)
分类号: TP391  
出版年,卷(期):页码: 2011 , 23 ( 12 ): 1949-1958 pdf下载
摘要: 对文献(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图;超多面体;最佳期望时间
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)
abstract: 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.
keyword: Delaunay triangulation; Voronoi diagram; hyper polyhedron; expected optimization time
 
Copyright © 2004《计算机辅助设计与图形学学报》版权所有
电话:010-62600342 传真:010-62562491
E_mail:jcad@ict.ac.cn