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

• 作 者: 汪嘉业 杨承磊 张彩明 吕琳
• 机 构: 山东财经大学计算机科学与技术学院,山东大学计算机科学与技术学院,山东省数字媒体技术重点实验室,山东省软件工程重点实验室
• 出 处: 计算机辅助设计与图形学学报
• 发表日期: 2011年12期
• 关键词: DELAUNAY三角化 VORONOI图 超多面体 最佳期望时间 Delaunay triangulation Voronoi diagram hyper po
• 基金项目: 国家自然科学基金（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维空间中任意凸的超多面体.证明了如果站点是独立地从一致分布在凸的超多面体的点集中取出,在线性期望时间内可对站点集实现Delauna