数值计算与计算机应用
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  联系我们 |  重点论文 |  在线办公 | 
数值计算与计算机应用  2011, Vol. 32 Issue (2): 135-142    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
弱非均匀 Voronoi 图细胞面积/体积的快速近似算法
方乐1,2, 洪洁瑛3
1. 法国里昂中央理工大学流体声学研究室, 69134 Ecully, 法国;
2. 中法联合实验室, 北京航空航天大学, 北京 100191;
3. 法国图卢兹经济学院, 31000 Toulouse, 法国
A RAPID APPROXIMATE ALGORITHM FOR COMPUTING THE AREAS/VOLUMES OF THE CELLS IN WEAKLY INHOMOGENEOUS VORONOI DIAGRAM
Fang Le1,2, Hong Jieying3
1. LMFA, Ecole Centrale de Lyon, Université Lyon, 69130 Ecully, France;
2. Laboratoire International Associé, Beihang University, Beijing 100191, China;
3. Toulouse School of Economics, 31000 Toulouse, France
 全文: PDF (1163 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 

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

服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词Voronoi图   图论   流体力学   有限差分法     
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 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 even better. 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.

Key wordsVoronoi diagram   graph theory   fluid mechanics   finite difference method   
收稿日期: 2010-08-13;
引用本文:   
. 弱非均匀 Voronoi 图细胞面积/体积的快速近似算法[J]. 数值计算与计算机应用, 2011, 32(2): 135-142.
. A RAPID APPROXIMATE ALGORITHM FOR COMPUTING THE AREAS/VOLUMES OF THE CELLS IN WEAKLY INHOMOGENEOUS VORONOI DIAGRAM[J]. Journal of Numerical Methods and Computer Applicat, 2011, 32(2): 135-142.
 
[1] Voronoi G. Nouvelles applications des parametres continus à la thèorie des formes quadratiques[J]. Journal für die Reine und Angewandte Mathematik, 1907, 133: 97-178.
[2] Mercier F and Baujard O. Voronoi diagrams to model forest dynamics in French Guiana[C]. Proceedings of GeoComputation ’97 & SIRC ’97, 1997.
[3] Liu G R and Liu M B. Smoothed particle hydrodynamics: a meshfree particle method[M]. 2003.
[4] Fortune S. A sweepline algorithm for voronoi diagrams[C]. Proceedings of the second annual symposium on Computational geometry, 1986, 313-322.
[5] Dyer M E and Frieze A M. On the complexity of computing the volume of a polyhedron[J]. SIAM J. Comput., 1988, 17: 967-974.
[6] Chaniotis A K, Poulikakos D, and Koumoutsakos P. Remeshed smoothed particle hydrodynamics for the simulation of viscous and heat conducting flows[J]. Journal of Computational Physics, 2002, 182: 67-90.
[7] Guilcher P M. Contribution au developpement d’une methode SPH pour la simulation numérique des interactions houle-structure[D]. PhD thesis, Ecole Centrale de Nante, 2008.
[8] Wei Y, Fang L, Cotin S, and Ma S. Interactive blood-coil simulation using discrete exterior calculus[C]. ICVFM, Caserta, 2010.
[9] Jiang Y S, Fang L, Jing X D, Sun X F, and Leboeuf F. A second-order numerical method for elliptic equations with singular sources using local filter[J]. Computers & Fluids, submitted.
[10] CGAL, http://www.cgal.org/ [OL].
[1] 赵慧勇, 雷波, 黄为民, 乐嘉陵. TNT k-omega湍流模型的隐式解法及其在超声速流动模拟中的应用[J]. 数值计算与计算机应用, 2010, 31(2): 108-115.
[2] 金君,乔楠,梁德旺. NAPA软件的并行优化[J]. 数值计算与计算机应用, 2008, 29(1): 65-72.
[3] 吴泽艳,薛晓春. FDTD计算中一种UPML吸收边界与其内部计算区域的统一建模方法[J]. 数值计算与计算机应用, 2008, 29(1): 8-14.
[4] 陈静,罗振东,孙萍,. 定常的磁流体力学方程的非线性Galerkin—Petrov最小二乘混合元法[J]. 数值计算与计算机应用, 2007, 29(4): 421-432.
[5] 王珏,张法勇,. 带有多项式非线性项的高维反应扩散方程有限差分格式的长时间行为[J]. 数值计算与计算机应用, 2007, 29(2): 177-188.
Copyright © 2008 数值计算与计算机应用 版权所有
中国科学院数学与系统科学研究院 《数值计算与计算机应用》编辑部
北京2719信箱 (100190) Email: szjs@lsec.cc.ac.cn
Support by Beijing Magtech Co.ltd   E-mail:support@magtech.com.cn
京ICP备05002806号-10