期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

E^d带权点集的Regular三角化的构造算法 被引量：3

Algorithm for Constructing the Regular Triangulation of a Set of Weighted Points in E^d
下载PDF
导出
摘要 该文提出了一种构造带权点集的Regular三角化的算法,此算法统一了构造点集的Delauany三角化的Bowyer/Waston算法.如果采用一种称为Delaunay树的数据结构来辅助点的定位,则算法的效率为 O（nlogn+n[d/2]）.与Edelsbrunner和Shah提出的局部变换算法相比,此算法从理论和实现两方面都要简单一些.算法可以应用到曲线曲面重构和分子建模等领域. This paper puts forward an algorithm for constructing the regular triangulation of a set of weighted points in Ed. The algorithm unifies and extends the Bowyer/Waston algorithm for the Delaunay triangulation construction. The time complexity of this algorithm is equal to O (nlogn+n[d/2]), if an auxiliary data structure called Delaunay Tree is used in it. Compared with the local transformation algorithm proposed by Edelsbrunner and Shah, this algorithm is simpler in theory and implementation. It can be applied to the fields of curve/surface reconstruction and molecule modeling.
作者 吴壮志 怀进鹏 杨钦
机构地区 北京航空航天大学计算机科学与工程系
出处 《计算机学报》 EI CSCD 北大核心 2002年第11期1243-1249,共7页 Chinese Journal of Computers
关键词 E^d带权点集 Regular三角化 构造算法 Power距离 带权alpha复形 数据结构 Power distance, Regular triangulation, weighted Delaunay triangulation, weighted alpha complex
分类号 TP311.12 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献10

  • 1Bowyer A.Computing dirichlet tessellations[].Computer Journal.1981
  • 2Edelsbrunner H,Mucke E P.Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms[].ACM Transactions on Graphics.1990
  • 3Edelsbrunner H,Shah N R.Incremental topological flipping works for regular triangulations[].In: Proc the th Annual ACM Symposium on Computational Geometry Berlin Germany.1992
  • 4Facello M.Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions[].Computer Aided Geometric Design.1995
  • 5Vigo M.Two simple flipping algorithms for computing regular triangulations in the plane[]..2000
  • 6Eelsbrunner H.Weighted alpha shapes[]..1992
  • 7Boissonat J,Teillaud M.On the randomized construction of the Delaunay tree[].Theoretical Computer Science.1993
  • 8Aurenhammer F.Voronoi diagram-A survey of a fundamental geometry data structure[].ACM Computing Surveys.1991
  • 9Lawson C L.Generation of a triangular grid with applications to contour plotting[]..1972
  • 10Lawson CL.Software for C1surface interpolation[].Mathematical Software III.1977

同被引文献31

  • 1孟宪海,李吉刚,杨钦.带权优化约束Delaunay三角化算法[J].北京航空航天大学学报,2005,31(12):1284-1288. 被引量：7
  • 2Ruppert J.A Delaunay refinement algorithm for quality 2-dimensional mesh generation[J].Journal of Algorithms,1995,18(3):548～585
  • 3Shewchuk J R.Tetrahedral mesh generation by Delaunay refinement[A].Proceedings of the 14th ACM Symposium on Computational Geometry[C].New York:ACM,1998.86～95
  • 4Shewchuk J R.Delaunay refinement algorithms for triangular mesh generation[J].Computational Geometry,2002,22(1-3):21～74
  • 5Cheng S W,Dey T K.Quality meshing with weighted Delaunay refinement[A].Proceeding of the 13th ACM-SIAM Symposium on Discrete Algorithms[C].New York:ACM-SIAM Press,2002.137～146
  • 6Li X Y.Generating well-shaped d-dimensional Delaunay meshes[J].Theoretical Computer Science,2003,296(1):145～165
  • 7Cheng S W,Dey T K,Edelsbrunner H,et al.Silver exudation[J].Journal of the ACM,2000,47(5):883～904
  • 8Murphy M,Mount D M,Gable C W.A point-placement strategy for conforming Delaunay tetrahedralization[A].Proceeding of the 11th ACM-SIAM Symposium on Discrete Algorithms[C].New York:ACM,2000.67～74
  • 9Cohen-Steiner D,De Verdiere E C,Yvinec M.Conforming Delaunay triangulations in 3D[A].Proceeding of the 18th Annual Symposium on Computational Geometry[C].New York:ACM,2002.199～208
  • 10Cheng S W,Poon S H.Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio[A].Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms[C].New York:ACM,2003.295～304

引证文献3

二级引证文献16

计算机学报
2002年 第11期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部