| 摘要: |
| 提出采用黎曼流形描述研究对象和基于坐标卡生成Voronoi图的算法思路.讨论了黎曼流形上研究Voronoi图的难点,并给出了存在定理,该定理说明了坐标卡上Voronoi图的存在条件.按照算法思路和存在定理,详细描述了二维黎曼流形上创建坐标卡的算法,并给出流形上转换函数和混合函数的定义方法.最后描述了基于坐标卡生成Voronoi图的算法,并给出了具体实例. |
| 关键词: 二维黎曼流形 坐标卡 Voronoi图 Delaunay三角化 存在性 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the Beijing Municipal Natural Science Foundation of China under Grant No.4062010 (北京市自然科学基金) |
|
| Algorithm for Creating Voronoi Diagrams for Two-Dimensional Riemannian Manifolds |
|
HENG Dan,YANG Qin,LI Ji-Gang,CAI Qiang
|
| Abstract: |
| This paper describes objects by Riemannian manifolds and creates Voronoi diagrams based on charts. Difficulties in studying Voronoi diagrams for Riemannian manifolds are discussed. A theorem in existence is given, which demonstrates the present condition of Voronoi diagrams for Riemannian manifolds in a chart. According to the idea and theorem, this paper describes the algorithm of creating charts for two-dimensional Riemannian manifolds and presents the definitions of transition and blend functions. Finally, the algorithm of creating Voronoi diagrams based on charts is given, and some examples are provided. |
| Key words: two-dimensional Riemannian manifold chart Voronoi diagram Delaunay triangulation existence |
