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

A RAPID APPROXIMATE ALGORITHM FOR COMPUTING THE AREAS/VOLUMES OF THE CELLS IN WEAKLY INHOMOGENEOUS VORONOI DIAGRAM

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

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 more ＂virtual flow fields＂ are 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. One virtual field can bring an acceptable error, while using two virtual fields together is evenbetter. This research aims at providing a new idea, that the continuous difference equations may be applied to approximately investigate the discontinuous problems in graph theory.