| 弱非均匀Voronoi图细胞面积／体积的快速近似算法 |
| |
| 引用本文： | 方乐,洪洁瑛.弱非均匀Voronoi图细胞面积／体积的快速近似算法[J].数值计算与计算机应用,2011,32(2):135-142. |
| |
| 作者姓名： | 方乐 洪洁瑛 |
| |
| 作者单位： | 1. 法国里昂中央理工大学流体声学研究室,69134 Ecully,法国;中法联合实验室,北京航空航天大学,北京,100191
2. 法国图卢兹经济学院,31000 Toulouse,法国 |
| |
| 摘 要： | 本文针对弱非均匀Voronoi图，介绍一种计算细胞面积／体积的新型快速近似算法．该算法引入一组或多组“虚拟流场”，利用流体力学连续方程的差分近似，得到Voronoi细胞间的递推关系．该算法的优点是复杂度低，递推公式简单，容易在计算机上实现．通过算例研究了各种情况下的误差大小，采用单虚拟流场已经可以得到可以接受的误差范围，而采用双虚拟流场更能进一步减小此误差．本文的目的旨在提供一个全新的思路，通过连续的微分方程来近似考虑离散的图论问题．
|
| 关 键 词： | Voronoi图 图论 流体力学 有限差分法 |
A RAPID APPROXIMATE ALGORITHM FOR COMPUTING THE AREAS/VOLUMES OF THE CELLS IN WEAKLY INHOMOGENEOUS VORONOI DIAGRAM |
| |
| Fang Le,Hong Jieying.A RAPID APPROXIMATE ALGORITHM FOR COMPUTING THE AREAS/VOLUMES OF THE CELLS IN WEAKLY INHOMOGENEOUS VORONOI DIAGRAM[J].Journal on Numerical Methods and Computer Applications,2011,32(2):135-142. |
| |
| Authors: | Fang Le Hong Jieying |
| |
| Affiliation: | Fang Le (LMFA,Ecole Centrale de Lyon,Universite Lyon,69130 Ecully,France,Laboratoire International Associe,Beihang University,Beijing 100191,China) Hong Jieying (Toulouse School of Economics,31000 Toulouse,France) |
| |
| Abstract: | In order to deal with the weakly inhomogeneous Voronoi diagrams,we introduce a new rapid approximate algorithm for computing the aeras/volumes of the cells.One or morevirtual flow fieldsare introduced,which can lead to the recursion relation between Voronoi cells by applying the continuous equation of fluid mechanics.This new algorithm has low complexity and simple recursion formulas,and is easy to be implemented in computer programming.A test case is then used to evaluated the error of this new algorithm.O... |
| |
| Keywords: | Voronoi diagram graph theory fluid mechanics finite difference method |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
