Voronoi Diagrams: Properties and Applications | IB数学：Voronoi图的性质与应用

📚 Voronoi Diagrams: Properties and Applications | IB数学：Voronoi图的性质与应用

A Voronoi diagram is a way of dividing a plane into regions based on distance to a set of points. Each point in a given region is closer to that region’s generating site than to any other site. This concept appears in the IB Mathematics Analysis and Approaches and Applications and Interpretation syllabuses, especially in the context of coordinate geometry and optimisation problems.

Voronoi图是一种根据到一组点的距离将平面划分成若干区域的方法。给定区域内的每一点，到达该区域生成点（站点）的距离，比到达其他任何站点的距离都更近。这一概念出现在IB数学分析与方法（AA）以及应用与解释（AI）课程中，尤其在坐标几何与最优化问题中经常出现。

1. What Is a Voronoi Diagram | 什么是Voronoi图

A Voronoi diagram is constructed from a finite set of points called sites or generators. For each site, the corresponding Voronoi cell is the set of all points in the plane that are closer to that site than to any other site. The boundaries between adjacent cells are line segments that lie on the perpendicular bisectors of the segments joining the two sites.

Voronoi图由一组有限点构造而成，这些点称为站点（sites）或生成点（generators）。对于每个站点，对应的Voronoi单元（cell）是平面中所有到该站点比到其他任何站点都更近的点的集合。相邻单元之间的边界，位于连接两个站点的线段的垂直平分线上。

2. Constructing a Voronoi Diagram | 构造Voronoi图

To construct a Voronoi diagram manually with two sites A and B, first draw the perpendicular bisector of segment AB. This line separates the plane into two half-planes: one containing points closer to A, and the other containing points closer to B. For more than two sites, the process is repeated for every pair of sites, and the final cells are the intersections of the relevant half-planes. In IB examinations, you rarely draw the full diagram; instead, you calculate equations of bisectors and locate intersection points.

要手工构造两个站点A和B的Voronoi图，首先画出线段AB的垂直平分线。这条线将平面分成两个半平面：一个包含离A更近的点，另一个包含离B更近的点。对于多于两个站点的情况，对每一对站点重复上述过程，最终单元是相关半平面的交集。在IB考试中，通常不需要画出完整的图形，而是计算垂直平分线的方程并求出交点。

3. Perpendicular Bisectors | 垂直平分线

Given two sites A(x₁, y₁) and B(x₂, y₂), the perpendicular bisector of AB is the line consisting of all points P(x, y) such that PA = PB. Using the distance formula:

√[(x − x₁)² + (y − y₁)²] = √[(x − x₂)² + (y − y₂)²]

Squaring both sides and simplifying gives a linear equation. This line is the boundary between the cells of A and B. Any point on the line is exactly equidistant from both sites.

给定两个站点A(x₁, y₁)和B(x₂, y₂)，AB的垂直平分线是满足PA = PB的所有点P(x, y)组成的直线。利用距离公式：

√[(x − x₁)² + (y − y₁)²] = √[(x − x₂)² + (y − y₂)²]

两边平方并化简，得到一个线性方程。这条线就是A和B两个单元之间的边界。直线上的任意点到两个站点的距离相等。

4. Voronoi Cells and Nearest Site | Voronoi单元与最近站点

Each Voronoi cell is a convex polygon (possibly unbounded for sites on the edge of the diagram). A point inside a cell is strictly closer to its site than to all other sites. This “nearest site” property makes Voronoi diagrams extremely useful for problems such as finding the nearest hospital, school, or mobile phone tower from a given location. In IB problems, you may be asked to determine which site a given point belongs to by comparing distances or using the bisector equations.

每个Voronoi单元是一个凸多边形（位于图形边缘的站点对应的单元可能无界）。单元内的点严格地比到其他任何站点都更靠近其所在单元的站点。这种“最近站点”性质使Voronoi图在解决“最近的医院、学校或手机信号塔在哪里”等问题时非常有用。在IB题目中，可能会要求你通过比较距离或使用垂直平分线方程，判断给定点属于哪个站点。

5. Adding a New Site | 添加新站点

When a new site is added to an existing Voronoi diagram, it will “steal” a region from surrounding cells. The new cell is bounded by perpendicular bisectors between the new site and each nearby existing site. In examination questions, you might be given four sites and asked to find the equation of the boundary after inserting a fifth site. The strategy is always the same: find the perpendicular bisector between the new site and the relevant old site, then restrict it to the region where the new site is actually closer.

当在已有的Voronoi图中添加一个新站点时，它会从周围的单元中“夺走”一部分区域。新单元由新站点与附近每个已有站点之间的垂直平分线围成。在考题中，可能会给出四个站点，并让你求出插入第五个站点后边界的方程。解题策略始终相同：求出新站点与相关旧站点之间的垂直平分线，然后将其限制在新站点确实更近的区域内。

6. Empty Circles and Three Sites | 空圆与三个站点

A key property of a Voronoi vertex is that it is equidistant from three or more sites. At such a vertex, the circumcircle of the three sites passes through those sites and contains no other sites in its interior. This is called an empty circle. In IB problems, you may be asked to find the coordinates of a Voronoi vertex by solving the equations of two perpendicular bisectors, or by calculating the circumcentre of a triangle formed by three sites.

Voronoi顶点的一个关键性质是：它到三个或更多站点的距离相等。在这样的顶点处，由这三个站点确定的圆经过这些站点，并且圆内不包含其他任何站点。这称为空圆（empty circle）。在IB题目中，可能会要求通过联立两条垂直平分线的方程来求Voronoi顶点的坐标，或者计算由三个站点构成的三角形的外心。

7. Coordinate Geometry with Voronoi Diagrams | Voronoi图的坐标几何

Many IB questions provide coordinates of sites and ask you to compute boundary equations, distances, or areas. For example, given sites A(2, 3) and B(6, 7), the perpendicular bisector is found by setting PA² = PB²:

(x − 2)² + (y − 3)² = (x − 6)² + (y − 7)²

Expanding: x² − 4x + 4 + y² − 6y + 9 = x² − 12x + 36 + y² − 14y + 49. Simplifying gives 8x + 8y = 72, or x + y = 9. This line is the boundary between the cells of A and B.

许多IB问题会给出站点的坐标，并要求计算边界方程、距离或面积。例如，给定站点A(2, 3)和B(6, 7)，通过令PA² = PB²求出垂直平分线：

(x − 2)² + (y − 3)² = (x − 6)² + (y − 7)²

展开：x² − 4x + 4 + y² − 6y + 9 = x² − 12x + 36 + y² − 14y + 49。化简得8x + 8y = 72，即x + y = 9。这条线就是A和B两个单元之间的边界。

8. Using Voronoi Diagrams to Solve Location Problems | 利用Voronoi图解决选址问题

Suppose four coastal towns are located at given coordinates, and you need to choose a point for a new lifeboat station so that the maximum distance to any town is as small as possible. The optimal point is a Voronoi vertex, because at such a point the distance to the three surrounding sites is equal, and no other point can improve the worst-case distance. In IB questions, you may be asked to identify which vertex is optimal and justify your choice.

假设四个沿海小镇位于给定坐标处，你需要选择一个新救生艇站的位置，使得到任何小镇的最大距离尽可能小。最优点是一个Voronoi顶点，因为在这样的点处，到周围三个站点的距离相等，任何其他点都不能改善最坏情况下的距离。在IB问题中，可能会要求你识别哪个顶点是最优的，并证明你的选择。

9. Worked Example: Finding a Voronoi Vertex | 例题：求Voronoi顶点

Consider three sites A(0, 0), B(4, 0), C(0, 6). The perpendicular bisector of AB is x = 2. The perpendicular bisector of AC is y = 3. Solving these gives the Voronoi vertex V(2, 3). Check the distance from V to each site: VA = √(4 + 9) = √13, VB = √(4 + 9) = √13, VC = √(4 + 9) = √13. Indeed, V is equidistant from all three sites. In a larger diagram, you would also verify that no other site lies inside the circle centred at V with radius √13.

考虑三个站点A(0, 0)、B(4, 0)、C(0, 6)。AB的垂直平分线是x = 2。AC的垂直平分线是y = 3。联立解得Voronoi顶点V(2, 3)。验证V到各站点的距离：VA = √(4 + 9) = √13，VB = √(4 + 9) = √13，VC = √(4 + 9) = √13。确实，V到三个站点距离相等。在更大的图形中，还需要验证没有其他站点位于以V为圆心、半径为√13的圆内。

10. Applications and Limitations | 应用与局限

Voronoi diagrams appear in many real-world contexts: epidemiology (mapping closest health clinics), urban planning (school zoning), biology (territorial behaviour of animals), and computer graphics (procedural terrain generation). However, the standard Euclidean Voronoi diagram assumes straight-line distance. In real life, travel distance may be affected by roads, rivers, or mountains, so weighted or network Voronoi diagrams are sometimes used. For the IB syllabus, you only need to master the Euclidean case and its key properties.

Voronoi图在许多现实场景中都有应用：流行病学（绘制最近的诊所）、城市规划（学校分区）、生物学（动物的领地行为）以及计算机图形学（程序化地形生成）。然而，标准的欧几里得Voronoi图假设的是直线距离。在现实生活中，出行距离可能受到道路、河流或山脉的影响，因此有时会使用加权或网络Voronoi图。对于IB课程，只需要掌握欧几里得情形及其关键性质即可。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Voronoi Diagrams: Properties and Applications | IB数学：Voronoi图的性质与应用