刘　欣,李海明，刘颖华

(承德石油高等专科学校 社科与数理部，河北　承德　067000)



Voronoi图的性质及离散构造综述

刘欣,李海明，刘颖华

(承德石油高等专科学校 社科与数理部，河北承德067000)

摘要：本文给出Voronoi图的背景和定义以及应用概述，在介绍传统算法的基础上，介绍扩展Voronoi图的离散构造算法，即直接从离散的生成元点出发，而不需要考虑生成元的具体形状，避免了对Voronoi边的形状的计算，对使用计算机算法提供了有效依据。

关键词：Voronoi图；离散Voronoi图；离散构造

Voronoi图概念最早源于以下自然问题：宇航员研究宇宙结构；考古学家试图识别不同部落影响下的地区；气象学家在仪器不灵时估算降雨(雪)量；城市规划者在城市中进行公共学校定位[1]；物流园区范围的设定等。它们虽然表面涉及了完全不同的现象，但具有一点共同之处，即都可以用Voronoi图的概念来解决。

1Voronoi图背景

1.1Voronoi图的定义

给定平面上有限个(大于1个)孤立点的集合，我们依照欧氏距离将平面上的所有位置点分配给点集中距它最近的点。结果将平面分成了一个网格，这个网格中的区域与平面给出的点集有关，我们称这个网格为由这个点集生成的平面普通Voronoi图，形成Voronoi图的区域为普通Voronoi多边形。在不混淆的情况下，简称普通Voronoi图为Voronoi图，普通Voronoi多边形为Voronoi多边形。

下面给出精确的数学语言描述：

定义设P={p1,…,pn}∈R2,2≤n<∞,xi≠xj(i≠j),i,j∈In={1,…,n}，称由下式

(1)

给出的区域为与点pi关联的普通平面Voronoi多边形，由Vor={V(p1),…,V(pn)}给出的集合为由P生成的平面普通Voronoi图[2](或简称P的Voronoi图)。我们称Voronoi多边形的顶点为Voronoi顶点，V(pi)中的pi为生成元点，集合P={p1,…,pn}为Voronoi图Vor的生成元集。……