Voronoi图
原始Voronoi图
我们考虑一个包含n个在欧式平面R2的点的集合S={s1,……,s~n}，其中2≤n<∞。这n个点的笛卡尔坐标分别为(s11,s12),……(sn1,sn2)，并且这些点并不重合。集合S中的点我们称之为站点(sites)。设x为欧式空间中的任一点，坐标为(x1,x2)。我们设点x和一个站点si∈S的距离为
d
E
(
s
i
,
x
)
=
∣
∣
s
i
−
x
∣
∣
=
(
(
s
i
1
−
x
1
)
2
)
+
(
s
i
2
−
x
2
)
2
)
2
(1)
d_E(s_i,x)=||s_i-x||=\sqrt[2]{((s_{i1}-x_1)^2)+(s_{i2}-x_2)^2)}\tag{1}
dE(si,x)=∣∣si−x∣∣=2((si1−x1)2)+(si2−x2)2)(1)
如果
s
i
∈
S
s_i\in S
si∈S是离x距离最近的站点或离x距离最近的站点之一，我们可以得知对于其他任一点
s
j
∈
S
,
j
∈
I
n
s_j\in S,j \in I_n
sj∈S,j∈In都有
d
E
(
s
i
,
x
)
<
d
E
(
s
j
,
x
)
d_E(s_i,x)<d_E(s_j,x)
dE(si,x)<dE(sj,x)。我们将所有符合条件的x的集合称为
s
i
s_i
si控制的原始Voronoi区域，表示为
V
E
(
s
i
)
=
{
x
∣
d
E
(
s
i
,
x
)
⩽
d
E
(
s
j
,
x
)
,
i
≠
j
,
j
∈
I
n
}
V_E(s_i)=\{x|d_E(s_i,x)\leqslant d_E(s_j,x),i\neq j,j\in I_n\}
VE(si)={x∣dE(si,x)⩽dE(sj,x),i=j,j∈In}
我们称所有站点控制区域组成的集合位原始Voronoi图，定义为
V
E
(
S
)
=
{
V
E
(
s
i
)
,
…
…
,
V
E
(
s
n
)
}
V_E(S)=\{V_E(s_i),……,V_E(s_n)\}
VE(S)={VE(si),……,VE(sn)}
两个不同站点控制的区域的划分线，是垂直于
s
i
和
s
j
s_i和s_j
si和sj连接线的垂直平分线，这条线把平面分为两部分，每个站点控制区域内得点距离改点的距离都小于到另一个站点的距离。
权重Voronoi图
在包含n个站点的集合S划分的原始Voronoi图中，包含了一个隐含的条件，即每个站点除了位置不同外其他都是相同的，换句话说就是每一个站点都有相同的权重。在这个基础上进行扩展，假设有一组参数
W
=
{
w
i
∣
i
∈
{
1
,
…
…
,
n
}
}
W=\{w_i|i \in \{1,……,n\}\}
W={wi∣i∈{1,……,n}}，这组参数我们称之为权重。通过使用权重函数，我们可以定义权重距离来生成权重Voronoi图
V
(
S
,
W
)
V(S,W)
V(S,W)。站点
s
i
s_i
si控制的Voronoi区域
V
(
s
i
,
w
i
)
∈
V
(
S
,
W
)
V(s_i,w_i) \in V(S,W)
V(si,wi)∈V(S,W)不仅取决于站点的位置，还取决于站点的权重，通常权重较大的站点形成更大的Voronoi区域。由于权重距离允许多种函数形式，因此存在各种各样的具有不同特点的权重Voronoi剖分。这里重点介绍两种权重距离函数，它们的连通区域特别适合计算容量限制的Voronoi图。
加权Voronoi图（Additively Weighted Voronoi Diagrams）
一个加权Voronoi图
V
A
W
(
S
,
W
)
V_{AW}(S,W)
VAW(S,W)由以下距离函数表征，其中站点
s
i
∈
S
s_i\in S
si∈S，它的权重
w
i
∈
W
w_i\in W
wi∈W，点x是平面上任一点。
d
A
W
(
s
i
,
w
i
,
x
)
=
∥
s
i
−
x
∥
−
w
i
d_{AW}(s_i,w_i,x) = \|s_i-x\|-w_i
dAW(si,wi,x)=∥si−x∥−wi.
两个站点
s
i
s_i
si和
s
j
s_j
sj的平分线的形状随参数值
α
=
∣
∣
s
i
−
s
j
∣
∣
\alpha = ||s_i-s_j||
α=∣∣si−sj∣∣和
β
=
w
i
−
w
j
\beta=w_i-w_j
β=wi−wj变化而变化，其中，我们不失一般性的假设
β
≥
0
\beta \geq 0
β≥0。如果
0
<
α
<
β
0<\alpha<\beta
0<α<β，则站点
s
i
s_i
si在整个平面上占主导地位，
s
j
s_j
sj控制的区域消失。如果
α
=
β
\alpha=\beta
α=β时，除由
s
i
s_i
si到
s
j
s_j
sj向外辐射的半线外，其他区域都消失。最后，如果
α
>
β
\alpha >\beta
α>β，则
V
A
W
(
s
i
,
w
i
)
V_{AW}(s_i,w_i)
VAW(si,wi)和
V
A
W
(
s
j
,
w
j
)
V_{AW}(s_j,w_j)
VAW(sj,wj)的平分线是以
s
i
和
s
j
s_i和s_j
si和sj为焦点的双曲线。这里需要注意一点，如果
β
=
0
\beta = 0
β=0，平分线就还是两个站点连线的垂直平分线。
幂图(Power Diagrams)
一个幂图
V
P
W
(
S
,
W
)
V_{PW}(S,W)
VPW(S,W)又称为加权幂次Voronoi图(additively weighted power voronoi diagram)，它的特点是使用PW距离函数，如下所示
d
P
W
(
s
i
,
w
i
,
x
)
=
∣
∣
s
+
i
−
x
∣
∣
2
−
w
i
d_{PW}(s_i,w_i,x) = {||s+i-x||}^2-w_i
dPW(si,wi,x)=∣∣s+i−x∣∣2−wi.
这时，两个Voronoi区域
V
P
W
(
s
i
,
w
i
)
V_{PW}(s_i,w_i)
VPW(si,wi)和
V
P
W
(
s
j
,
w
j
)
V_{PW}(s_j,w_j)
VPW(sj,wj)的平分线是一条直线，它平行于线段
s
i
s
j
‾
\overline{s_is_j}
sisj的垂直平分线并且通过点
p
i
j
∗
p_{ij}^*
pij∗，
p
i
j
∗
p_{ij}^*
pij∗由下述公式给出：
p
i
j
∗
=
∣
∣
s
j
∣
∣
2
−
∣
∣
s
i
∣
∣
2
+
w
i
−
w
j
2
∣
∣
s
j
−
s
i
∣
∣
2
(
s
j
−
s
i
)
p_{ij}^* = \frac{||s_j||^2-||s_i||^2+w_i-w_j}{2||s_j-s_i||^2}(s_j-s_i)
pij∗=2∣∣sj−si∣∣2∣∣sj∣∣2−∣∣si∣∣2+wi−wj(sj−si).
如果
∣
∣
s
i
−
s
j
∣
∣
2
<
w
j
−
w
i
||s_i-s_j||^2<w_j-w_i
∣∣si−sj∣∣2<wj−wi，则站点
s
i
s_i
si会处在他控制的Voronoi区域
V
P
W
(
s
i
,
w
i
)
V_{PW}(s_i,w_i)
VPW(si,wi)外面。
质心Voronoi图
质心Voronoi图是一个限定边界在二维欧式空间的Voronoi图，它的性质是每一个Voronoi区域
V
(
s
i
)
V(s_i)
V(si)的站点都在区域质心
m
i
m_i
mi上，质心的计算公式由下给出：
m
i
=
∫
V
(
s
i
)
x
ρ
(
x
)
d
x
∫
V
(
s
i
)
ρ
(
x
)
d
x
m_i =\frac{\int_{V(s_i)}x\rho (x)dx}{\int_{V(s_i)}\rho (x)dx}
mi=∫V(si)ρ(x)dx∫V(si)xρ(x)dx
其中
ρ
(
x
)
≥
0
\rho(x) \geq 0
ρ(x)≥0是定义在空间
Ω
\Omega
Ω上的密度函数。换句话说，质心是Voronoi区域相对于密度函数的质量的中心。质心Voronoi图的重要性建立在他与能量函数的关系上：
F
(
S
,
V
(
S
)
)
=
∑
i
=
1
n
∫
x
∈
V
(
s
i
)
ρ
(
x
)
∣
∣
x
−
s
i
∣
∣
2
d
x
\mathscr{F}(S,\mathscr{V}(S)) = \sum_{i=1}^{n}\int_{x\in V(s_i)}\rho(x)||x-s_i||^2dx
F(S,V(S))=i=1∑n∫x∈V(si)ρ(x)∣∣x−si∣∣2dx
其中
V
(
s
i
)
∈
V
(
S
)
V(s_i)\in \mathscr{V}(S)
V(si)∈V(S)并且
s
i
∈
S
s_i\in S
si∈S。对于
F
\mathscr{F}
F最小化的必须条件是
V
(
S
)
\mathscr{V}(S)
V(S)是关于
S
S
S的一个Voronoi图。
生成质心Voronoi图的一个常用方法是Lloyd迭代法。该算法迭代地移动每个站点
s
i
∈
S
s_i\in S
si∈S到它控制的Voronoi区域
V
(
s
i
)
∈
V
(
S
)
V(s_i) \in \mathscr{V}(S)
V(si)∈V(S)的质心
m
i
m_i
mi处，知道站点满足一定的收敛条件。由于站点每一次向质心移动都会影响到上述能量函数，算法可以使
F
\mathscr{F}
F收敛到它的局部最小值，即每个站点都与它控制区域的质心位置重合。[1]
容量限制Voronoi图(Capacity-Constrained Voronoi Diagrams)
考虑一个包含n个站点的集合
S
S
S，该集合确定了空间
Ω
∈
R
2
\Omega\in \mathbb{R}^2
Ω∈R2中符合密度函数
ρ
(
x
)
≥
0
，
x
∈
Ω
\rho(x) \geq 0，x\in \Omega
ρ(x)≥0，x∈Ω的一个Voronoi图
V
(
S
)
\mathscr{V}(S)
V(S)，其中每个站点的控制区域
V
(
s
i
)
∈
V
(
S
)
V(s_i)\in \mathscr{V}(S)
V(si)∈V(S)由该公式计算得到
∣
V
(
s
i
)
∣
=
∫
x
∈
V
(
s
i
)
ρ
(
x
)
d
x
|V(s_i)|=\int_{x\in V(s_i)}\rho(x)dx
∣V(si)∣=∫x∈V(si)ρ(x)dx.其中每个Voronoi区域面积
∣
V
(
s
i
)
∣
|V(s_i)|
∣V(si)∣被定义为站点
s
i
s_i
si的容量。
一个参数集合
C
=
{
c
i
∣
i
∈
{
1
,
…
…
,
n
}
}
，
0
≤
c
i
≤
∞
，
∑
C
=
∫
x
∈
Ω
ρ
(
x
)
d
x
C=\{c_i|i\in \{1,……,n\}\}，0\leq c_i \leq \infty，\sum C = \int_{x \in \Omega}\rho(x)dx
C={ci∣i∈{1,……,n}}，0≤ci≤∞，∑C=∫x∈Ωρ(x)dx，它被称为容量约束(
c
a
p
a
c
i
t
y
c
o
n
s
t
r
a
i
n
t
capacity\ constraint
capacity constraint)。一个容量约束的Voronoi图
V
(
S
,
C
)
\mathscr{V}(S,C)
V(S,C)就是由定义在
Ω
\Omega
Ω上的集合S划分的每个站点
s
i
∈
S
s_i\in S
si∈S都满足容量约束
c
i
∈
C
c_i\in C
ci∈C的Voronoi图。换句话说，一个由n个站点划定的容量限制Voronoi图和一组容量约束
C
C
C满足条件
∑
i
=
1
n
(
∣
V
(
s
i
)
−
c
i
∣
)
2
=
0
\sum_{i=1}^n(|V(s_i)-c_i|)^2=0
∑i=1n(∣V(si)−ci∣)2=0.
空间
Ω
\Omega
Ω可以是有界的也可以是无界的，只要符合密度
ρ
\rho
ρ的空间面积之和等于容量
C
C
C即可。
容量约束Voronoi图关注的是最终产生的Voronoi区域面积，而不是底层的站点位置，它的目的是确定给定空间的分区，这些分区由预定义大小的紧凑区域组成。因此，它并不局限于特定的空间或距离函数。