计算机辅助设计与图形学学报
計算機輔助設計與圖形學學報
계산궤보조설계여도형학학보
JOURNAL OF COMPUTER-AIDED DESIGN & COMPUTER GRAPHICS
2011年
12期
1949-1958
,共10页
汪嘉业%杨承磊%张彩明%吕琳
汪嘉業%楊承磊%張綵明%呂琳
왕가업%양승뢰%장채명%려림
Delaunay三角化%Voronoi图%超多面体%最佳期望时间
Delaunay三角化%Voronoi圖%超多麵體%最佳期望時間
Delaunay삼각화%Voronoi도%초다면체%최가기망시간
对文献(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三角化.该证明方法比较直观.虽然这类算法对输入点集有一致分布的要求,但在很多实际应用情况下这种要求常是被满足的,此时使用这类算法便可体现文中算法快速和易于实现的优点.
對文獻(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三角化.該證明方法比較直觀.雖然這類算法對輸入點集有一緻分佈的要求,但在很多實際應用情況下這種要求常是被滿足的,此時使用這類算法便可體現文中算法快速和易于實現的優點.
대문헌(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삼각화.해증명방법비교직관.수연저류산법대수입점집유일치분포적요구,단재흔다실제응용정황하저충요구상시피만족적,차시사용저류산법편가체현문중산법쾌속화역우실현적우점.
