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

• 作者: 吕琳 张彩明 杨承磊 汪嘉业
• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: Delaunay三角化 Voronoi图 超多面体 最佳期望时间
• 年，卷（期）: 2011,（12）
• 所属期刊栏目: 图形与可视化
• 页码范围: 1949-1958
• 分类号: TP391
• 字数: 8721字
• 语种: 中文

摘要

对文献(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三角化.该证明方法比较直观.虽然这类算法对输入点集有一致分布的要求,但在很多实际应用情况下这种要求常是被满足的,此时使用这类算法便可体现文中算法快速和易于实现的优点.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吕琳	山东大学计算机科学与技术学院	22	90	6.0	9.0
3	杨承磊	山东大学计算机科学与技术学院	34	356	10.0	18.0
5	张彩明	山东财经大学计算机科学与技术学院	17	113	5.0	9.0
16	汪嘉业	山东财经大学计算机科学与技术学院	2	7	1.0	2.0