关于一般图形Voronoi图的近似构造法的研究
Research on Voronoi Diagrams for General Figures by Approximation Structuring

张有会 ¹ 浅野哲夫 ² 小保方幸次 ²

文摘	随着计算机处理图形图象能力的增强，对计算几何理论与应用的研究，越来越为人们所重视。计算几何研究的是，如何高效处理通过视觉器官等途径得到的几何图形信息，开发高速解决几何问题的方法，从理论上探寻几何计算的复杂性与可行性，并对其性能做出评价。计算几何在计算机辅助设计、地理信息处理、计算机图形学以及机器人等领域都有着重要应用。Voronoi图是计算几何的一个重要分支。在计算几何中，Voronoi图理论成功地解决了找最近点，求最大空圆，求n个点的凸包，求最小树等问题。此外，Voronoi图在考古、生态研究、城市规划等领域也有许多重要应用。作者对于一般图形Voronoi图和对它用近似构造法得到的近似Voronoi图,提出用二者对应Voronoi边所围区域的面积作为近似程度的度量的观点,求出用点近似线段和用点近似圆弧时上述面积的计算公式,并对两点近似线段和两点近似圆弧时,影响近似程度的因素进行了分析,给出了母点设置原则和基于上述度量的近似构造方法。
其他语种文摘	Voronoi diagrams for general figures are ones built from generators, which include geometric diagrams, such as point, segment, arc, and so on. It was focused herein on Voronoi diagrams for general figures and approximation Voronoi diagrams approximation by approximation structuring. It was proposed that the area surrounded by Voronoi edges, for corresponding to the degree of approximation. Analysis for the factor of the degree of approximation was undergone, using twopoint approximation segment and two-point approximation arc. The principle of approximation structuring was at last provided.
来源	数值计算与计算机应用 ,2002,23(3):216-225 【核心库】
地址	1. 河北师范大学计算机系, 石家庄, 050016 2. 北陆先端科学技术大学院大学, 日本, 石川, 923-1292
语种	中文
文献类型	研究性论文
ISSN	1000-3266
学科	数学
文献收藏号	CSCD:1068979