维诺图

维诺图把平面分给一组点：每个点分到离它不比离其他点远的那片区域。画面是平面上的一扇窗，区域里的明暗只是为了好看。蓝色探针是一个空圆的圆心，圆的半径是它到最近的点的距离。在这一页，你可以挪动点，看邻居的区域怎样跟着变；让每块区域从自己的点长出来；看德劳内三角剖分；再把点匀开，让图案向蜂窝靠拢。

离点$p$不比离另一个点$q$远的点，组成一个半平面，边界是$pq$的垂直平分线。$p$的区域是这些半平面（每个别的点一个）的交集，所以是凸的。这些垂直平分线只有一部分成为边。区域和$p$的区域有公共边的点，是它的邻居；其余的半平面已经把整块区域包在里面。画框只是窗的边；一块区域伸到无穷远，当且仅当它的点落在所有点的凸包边界上。

三块或更多区域相交的顶点，离这些区域的点一样远，所以它是过这些点的圆的圆心。这个圆里没有点：要是有一个点在圆里，它离顶点就比这些点更近，顶点就该归它的区域了。通常一个顶点处正好三块区域相交。恰好四个点落在一个空圆上时，比如正方形格点，四块区域相交于一点；随机撒的点几乎不会这样。

“生长”让每个点以同样的速度长出一个圆盘。每个地方都先被离它最近的点够到，所以前沿正好在边上相遇。嵌入屏从侧面看同一个生长：在每个地方竖起高度，等于它到最近的点的距离，也就是立在各点上的圆锥$z = |x - s|$里最低的那一层；山脊就是边，生长就是水往上涨。最后被淹没的地方，是画框里地形的最高点，也就是圆心在画框里的最大空圆的圆心。

“三角剖分”把区域有公共边的两个点连起来；四个或更多点共用一个空圆时（比如正方形格点），再补上虚线的对角线。只要点不全在一条直线上，结果就是德劳内三角剖分。每个三角形的外接圆，就是围着一个顶点的那个空圆。

“匀开”一轮轮地把每个点挪到自己区域（裁到画框里）的重心，再重新分区域。这就是劳埃德算法。嵌入屏画出画框里一点到最近的点的平均平方距离，再除以画框面积与点数之比。每一轮都不会让它变大：点固定时，按最近的点分区域使它最小；区域固定时，把点放在重心使它最小。“蜂窝”那条线是一个下界，对应等面积正六边形、各点位于中心的理想排布。从随意撒的点出发，过程会停在附近的一个安定状态，而不是完美的蜂窝：通常还剩一些五边形和七边形挨在一起，像晶体里的位错。

维诺图以沃罗诺伊命名，他在1908年研究了任意维数的这种划分；三角剖分以德劳内命名，他在1934年描述了它。