弱非均匀Voronoi图细胞面积/体积的快速近似算法

摘要：

本文针对弱非均匀Voronoi图,介绍一种计算细胞面积/体积的新型快速近似算法.该算法引入一组或多组"虚拟流场",利用流体力学连续方程的差分近似,得到Voronoi细胞间的递推关系.该算法的优点是复杂度低,递推公式简单,容易在计算机上实现.通过算例研究了各种情况下的误差大小,采用单虚拟流场已经可以得到可以接受的误差范围,而采用双虚拟流场更能进一步减小此误差.本文的目的旨在提供一个全新的思路,通过连续的微分方程来近似考虑离散的图论问题.

关键词：Voronoi图、图论、流体力学、有限差分法

所属期刊栏目：32

分类号：V21;U41

在线出版日期：2011-09-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：135-142