黎曼流形的Delaunay三角化和Voronoi图

Delaunay triangulation and Voronoi diagrams for Riemannian manifolds

主要研究黎曼空间中Delaunay三角化和Voronoi图.首先,分析和讨论了黎曼流形的Delaunay三角化和Voronoi图的存在性和生成算法.然后,在分析已有研究成果基础上,给出了黎曼流形Delaunay三角化和Voronoi图的一些性质和证明,并提出了采用黎曼流形描述问题的必要性和使用坐标卡研究黎曼流形的优势和意义.最后,以二维流形为例,介绍了将模型初始数据解释为黎曼流形的算法,包括建立坐标卡,定义流形函数等.在黎曼流形定义的基础上,详细描述了基于坐标卡生成模型的Delaunay三角化和Voronoi图的算法,并给出具体实例.

Delaunay triangulation and Voronoi diagrams in Riemannian space were studied. Firstly, the existence and generation algorithm of Delaunay triangulation and Voronoi diagrams were discussed. Then on the basis of analysing the existed research achievements, some properties of Delaunay triangulation and Voronoi diagrams for Riemannian were given and proved. The necessities of describing object by Riemannian manifolds and advantages of researching Riemannian manifolds by charts were presented. Finally, taking 2- manifold as an example, the algorithm of getting Riemannian manifolds according to initial data of models was described, which included creating charts, defining functions of manifolds, and so on. The algorithm of crea- ting Delaunay triangulation and Voronoi diagrams of models based on charts was presented, and some examples were provided.