📚 Voronoi Diagrams | Voronoi 图
A Voronoi diagram is a geometric structure that partitions a plane into regions based on the distance to a given set of points, called sites. Each region, known as a Voronoi cell, consists of all points closer to its corresponding site than to any other site. This concept appears in many real-world contexts, from mapping mobile phone coverage to modelling natural territories.
Voronoi 图是一种几何结构，它根据到一组给定点（称为站点）的距离将平面划分成多个区域。每个区域称为一个 Voronoi 单元格，包含了所有离该站点比离其他任何站点都更近的点。这一概念出现在许多现实情境中，从绘制手机信号覆盖范围到模拟动物领地。
1. Defining Sites and Cells | 定义站点与单元格
The set of discrete points that generate the Voronoi diagram are called sites. Around each site, a Voronoi cell is formed by all points in the plane whose nearest site is that particular one. The boundaries between cells are where a point is equidistant to two or more sites.
生成 Voronoi 图的一组离散点称为站点。在每个站点周围都会形成一个 Voronoi 单元格，它由平面上所有离该站点最近的点组成。单元格之间的边界是到两个或更多站点距离相等的点的集合。
S = {s₁, s₂, ..., sₙ} is a set of sites, then the Voronoi cell for site sᵢ is V(sᵢ) = { x ∈ ℝ² | d(x, sᵢ) ≤ d(x, sⱼ) for all j ≠ i }.
数学上，若 S = {s₁, s₂, ..., sₙ} 是一组站点，则站点 sᵢ 的 Voronoi 单元格为 V(sᵢ) = { x ∈ ℝ² | 对所有 j ≠ i，d(x, sᵢ) ≤ d(x, sⱼ) }。
2. Edges, Vertices and the Perpendicular Bisector | 边、顶点与垂直平分线
In a Voronoi diagram, the shared boundaries between two adjacent cells are called edges. An edge is a portion of the perpendicular bisector of the line segment joining the two corresponding sites. A vertex is a point where three or more edges meet, and it is equidistant to the three nearest sites.
在 Voronoi 图中，两个相邻单元格之间的共享边界称为边。一条边是连接两个对应站点的线段的中垂线的一部分。顶点是三条或更多条边相交的点，它到三个最近站点的距离相等。
The perpendicular bisector is the set of points that are equidistant from two given points. Its construction is fundamental to drawing Voronoi diagrams by hand or algebraically.
垂直平分线是到两个给定点距离相等的点的集合。它的构造是手工或代数方法绘制 Voronoi 图的基础。
3. Constructing a Voronoi Diagram: Step by Step | 逐步构造 Voronoi 图
To construct a Voronoi diagram for a small set of sites manually, follow these steps: (1) Plot the sites on a coordinate plane. (2) For each pair of nearest sites, find the perpendicular bisector of the segment joining them. (3) Extend the bisectors until they intersect each other, keeping only the segments that are closer to the given sites than to any other. (4) The result is a set of convex polygons (cells) that together cover the entire plane.
对于一小组站点，可手工按以下步骤构造 Voronoi 图：(1) 在坐标平面上标出站点。(2) 对每对最近站点，求出它们连线段的垂直平分线。(3) 延长平分线直至它们相交，只保留离给定站点比离其他站点更近的线段。(4) 最终得到一组凸多边形（单元格），共同覆盖整个平面。
When working algebraically, the equation of a perpendicular bisector can be found using midpoint and negative reciprocal slope. For two points (x₁, y₁) and (x₂, y₂), the midpoint is M, and the slope of the bisector is the negative reciprocal of the segment's slope.
使用代数方法时，可通过中点与负倒数斜率求出垂直平分线方程。对于两点 (x₁, y₁) 和 (x₂, y₂)，中点为 M，平分线的斜率是线段斜率的负倒数。
4. Equation of a Perpendicular Bisector | 垂直平分线的方程
Given two sites A(xₐ, yₐ) and B(xb, yb), the perpendicular bisector can be derived. The midpoint M has coordinates ( (xₐ+xb)/2 , (yₐ+yb)/2 ). The slope of AB is mAB = (yb − yₐ)/(xb − xₐ), so the bisector's slope is mperp = −1/mAB (provided mAB ≠ 0).
给定两个站点 A(xₐ, yₐ) 和 B(xb, yb)，可以推导垂直平分线。中点 M 的坐标为 ( (xₐ+xb)/2 , (yₐ+yb)/2 )。线段 AB 的斜率为 mAB = (yb − yₐ)/(xb − xₐ)，因此平分线斜率为 mperp = −1/mAB（假设 mAB ≠ 0）。
The equation can then be written as y − yM = mperp (x − xM). Alternatively, using the distance condition: √[(x−xₐ)²+(y−yₐ)²] = √[(x−xb)²+(y−yb)²]. Squaring both sides and simplifying yields a linear equation, which is the perpendicular bisector.
方程可写为 y − yM = mperp (x − xM)。也可用距离条件：√[(x−xₐ)²+(y−yₐ)²] = √[(x−xb)²+(y−yb)²]。两边平方并化简，得到一个线性方程，即垂直平分线。
5. The Nearest Neighbour Property | 最近邻性质
The core property of a Voronoi diagram is that every point inside a cell is closer to its site than to any other site. This nearest-neighbour property allows us to determine which site a given location 'belongs to' by simply checking which cell contains the point.
Voronoi 图的核心性质是单元格内的每一点到其站点的距离都小于到其他任何站点的距离。这个最近邻性质使我们能够通过简单地判断一个点位于哪个单元格来确定它“属于”哪个站点。
To test whether a point P lies inside a particular cell of site A, verify that the distance from P to A is less than the distance from P to every other site. Alternatively, if the coordinates and perpendicular bisectors are known, evaluate the half-plane inequalities.
要检验点 P 是否位于站点 A 的特定单元格内，验证从 P 到 A 的距离小于 P 到其他所有站点的距离即可。或者，若已知坐标和垂直平分线，可计算半平面不等式。
6. Adding a New Site to a Voronoi Diagram | 向 Voronoi 图添加新站点
When an extra site is introduced, the diagram must be updated locally. The region affected is the set of existing cells that are closer to the new site than to their original site. The process involves drawing the perpendicular bisectors between the new site and each existing site that might be a nearest neighbour, then clipping the old cells.
当加入一个新站点时，必须局部更新 Voronoi 图。受影响的区域是那些到新站点比到原站点更近的现有单元格。该过程包括绘制新站点与每个可能成为最近邻的现有站点之间的垂直平分线，然后裁剪原有单元格。
Algorithmically, identify the cell that contains the new site, construct bisectors with its surrounding sites, and form a new cell for the added site. The edges of the new cell are segments of these bisectors. This local modification is efficient and is crucial in dynamic models.
算法上，先找出包含新站点的单元格，然后与周围站点构造中垂线，并为新站点形成新单元格。新单元格的边是这些平分线的线段。这种局部修改效率很高，在动态模型中很重要。
7. Largest Empty Circle | 最大空圆
The largest empty circle in a bounded region is centred either at a Voronoi vertex or at a site that lies on the boundary. Its radius is the distance from that centre to the nearest site. This circle contains no sites in its interior and is used in facility location problems, for instance to place a hazardous facility as far as possible from populated points.
在有界区域中，最大空圆的圆心要么落在 Voronoi 顶点上，要么落在位于边界的站点上。其半径是从该圆心到最近站点的距离。该圆内部不包含任何站点，常用于设施选址问题，例如将危险设施放置在尽可能远离居民点的位置。
To find the largest empty circle inside a convex polygon with sites, compute all Voronoi vertices, calculate the distance to the three nearest sites (which is the circle radius), and also check sites on the polygon boundary. The maximum radius among these candidates is the solution.
要找到含有站点集合的凸多边形内的最大空圆，需计算所有 Voronoi 顶点到三个最近站点的距离（即圆半径），同时检查多边形边界上的站点。候选圆心中的最大半径即为所求。
8. Nearest Neighbour Interpolation | 最近邻插值
Voronoi diagrams are the foundation for nearest neighbour interpolation, a simple method for estimating unknown values at query points based on known values at sites. The value assigned to any point is the value of the nearest site. This creates a step-like surface, where each cell has a constant value.
Voronoi 图是最近邻插值的基础，这是一种根据站点已知值估计查询点未知值的简单方法。分配给任意点的值就是最近站点的值。这会产生一个阶梯状表面，每个单元格的值恒定。
Although crude compared to linear or kriging interpolation, nearest neighbour interpolation is computationally fast and is widely used in geographic information systems and real-time rendering.
尽管与线性插值或克里金插值相比略显粗糙，但最近邻插值计算速度快，广泛用于地理信息系统和实时渲染。
9. Edge Cases and Degeneracies | 边界情况与退化
Degeneracies occur when four or more sites are cocircular, leading to a Voronoi vertex where more than three edges meet. In such cases, small perturbations can break the tie. While theoretically interesting, IB problems typically avoid degenerate configurations.
当四个或更多站点共圆时会发生退化现象，导致出现多于三条边相交的 Voronoi 顶点。这种情况下，微小的扰动即可打破平局。虽然理论上很有意思，但 IB 题目通常会避免退化结构。
If all sites are collinear, the Voronoi diagram consists of parallel perpendicular bisectors, creating unbounded strip-like cells that are not closed polygons. In an IB exam context, these situations are rarely tested, but understanding the geometry helps.
如果所有站点共线，Voronoi 图由平行的垂直平分线组成，形成无界的带状单元格而非封闭多边形。在 IB 考试中很少考查这些情况，但理解其几何结构会有所帮助。
10. Worked Example with Coordinates | 带坐标的完整示例
slope of AB = (8−4)/(6−2)=1, so bisector slope = −1. Equation: y−6 = −1(x−4) → y = −x+10.
考虑三个站点：A(2,4)、B(6,8) 和 C(8,2)。首先求 AB 的垂直平分线：中点 (4,6)，AB 斜率 = (8−4)/(6−2)=1，因此平分线斜率 = −1。方程：y−6 = −1(x−4) → y = −x+10。
midpoint (5,3), slope AC = (2−4)/(8−2)= −1/3, bisector slope = 3. Equation: y−3 = 3(x−5).
再求 BC 的平分线：中点 (7,5)，BC 斜率 = (2−8)/(8−6) = −3，所以平分线斜率 = 1/3。方程：y−5 = (1/3)(x−7)。类似地，对 AC：中点 (5,3)，AC 斜率 = (2−4)/(8−2)= −1/3，平分线斜率 = 3。方程：y−3 = 3(x−5)。
partitions the plane into three cells. Point P(5,5) can be tested for membership: d(P,A)=√10, d(P,B)=√10, d(P,C)=√18. P is equidistant to A and B, so lies on the edge between them.
解交点得到 Voronoi 顶点，组合相关线段将平面划分为三个单元格。可检验点 P(5,5) 的归属：d(P,A)=√10，d(P,B)=√10，d(P,C)=√18。P 到 A 和 B 的距离相等，故位于二者之间的边上。
11. Applications in Real Life | 现实生活中的应用
Voronoi diagrams are used in epidemiology to map disease spread, in ecology to model animal territories, in urban planning to determine service areas of schools or hospitals, and in computer graphics for motion planning and mesh generation. They also underpin cell tower coverage analysis and Wi-Fi signal mapping.
Voronoi 图被用于流行病学中绘制疾病传播图、生态学中模拟动物领地、城市规划中确定学校或医院的服务区域，以及计算机图形学中的运动规划和网格生成。它们同样支撑着手机基站覆盖分析和 Wi-Fi 信号地图。
In crystallography, Voronoi cells correspond to Wigner-Seitz cells, which describe the influence region of atoms in a lattice. The concept extends easily to higher dimensions and non-Euclidean distances.
在晶体学中，Voronnoi 单元格对应 Wigner-Seitz 原胞，用于描述晶格中原子的影响区域。该概念可轻松扩展到高维空间和非欧式距离。
12. Common Mistakes and Tips | 常见错误与提示
Students often confuse the perpendicular bisector of a segment with the segment itself, or miscalculate the negative reciprocal slope. Always double-check that the bisector passes through the midpoint. When adding a new site, remember that only cells that are nearer to the new site than to their original site are affected.
学生常常将线段的中垂线与线段本身混淆，或错误计算负倒数斜率。务必再次检查中垂线是否经过中点。添加新站点时，记住只有那些到新站点比到原站点更近的单元格才会受影响。
When determining the largest empty circle, do not forget to check boundary sites if the region is bounded. Also, use exact values and simplify radical expressions where possible, as IB often requires exact form.
在确定最大空圆时，如果区域有界，不要忘记检查边界上的站点。同时，应尽可能使用精确值并化简根式表达式，因为 IB 常要求精确形式。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图