IB Maths AI HL Voronoi Diagrams: Construction, Nearest Neighbour and Largest Empty Circle — IB 数学应用与解释 HL 沃罗诺伊图完整指南

沃罗诺伊图（Voronoi diagram）是 IB 数学「应用与解释」（Applications and Interpretation，简称 AI）课程中一道极具辨识度的题目，也是区分 AI 与「分析与方法」（Analysis and Approaches，简称 AA）两条路线的标志性内容之一。它从一张看似简单的散点图出发，把整个平面划分成若干「势力范围」，每一个点都属于离它最近的那个站点。本文将从最基本的定义讲起，一步步带你掌握垂直平分线的计算、沃罗诺伊图的构造方法、最近邻插值、最大空圆问题以及德劳内三角剖分，并用完整的例题演示考试中最常出现的三种题型。

The Voronoi diagram is one of the most recognisable topics in the IB Mathematics “Applications and Interpretation” (AI) course, and a signature piece of content that distinguishes the AI pathway from the “Analysis and Approaches” (AA) pathway. Starting from a seemingly simple scatter of points, it partitions the entire plane into “territories” so that every point belongs to whichever site is closest to it. This article begins with the most basic definitions and walks you step by step through the perpendicular bisector calculation, the construction of a Voronoi diagram, nearest neighbour interpolation, the largest empty circle problem, and Delaunay triangulation, before demonstrating the three most common exam question types with a complete worked example.

1. 什么是沃罗诺伊图：站点、单元与边界 | What Is a Voronoi Diagram: Sites, Cells and Boundaries

沃罗诺伊图处理的是这样一个问题：平面上有若干个固定点，称为「站点」（sites）；对于平面上任意一个位置，我们都希望立刻知道它离哪一个站点最近。把「离同一个站点最近」的所有点归成一类，就得到这个站点对应的「单元」（cell）。所有单元拼在一起、互不重叠、又恰好覆盖整个平面，这幅完整的划分图就是沃罗诺伊图。两个相邻单元的公共边界，叫做「边」（edge）；三条或更多边汇聚的交点，叫做「顶点」（vertex）。

A Voronoi diagram answers the following question: given a set of fixed points in the plane, called “sites,” for any location we want to know immediately which site is nearest to it. If we group together all points that are closest to the same site, we obtain that site’s “cell.” When all the cells are placed together, they do not overlap, yet they cover the entire plane exactly once; this complete partition is the Voronoi diagram. The common boundary between two adjacent cells is called an “edge,” and the point where three or more edges meet is called a “vertex.”

理解沃罗诺伊图最关键的一点是：单元边界上的每一个点到两侧站点的距离都恰好相等，单元内部的所有点到本单元站点的距离都严格小于到其他任何站点的距离。这个「到最近站点距离最小」的性质，正是沃罗诺伊图在现实世界中如此有用的根本原因，因为它天然回答了「谁离我最近」这类问题。

The single most important thing to understand is that every point on a cell boundary is exactly equidistant from the two sites on either side, while every point inside a cell is strictly closer to that cell’s site than to any other site. This “minimum distance to the nearest site” property is the fundamental reason the Voronoi diagram is so useful in the real world, because it naturally answers questions of the form “who or what is nearest to me?”

2. 垂直平分线：沃罗诺伊边界的数学基础 | The Perpendicular Bisector: The Maths Behind Every Cell Boundary

沃罗诺伊图中每一条边，本质都是两个站点之间线段的垂直平分线（perpendicular bisector）。要理解这一点，回想垂直平分线的定义：它是一条直线，其上的每一个点到线段两个端点的距离都相等。如果把两个站点看成线段端点，那么这条垂直平分线恰好就是把平面分成「离站点 A 更近」与「离站点 B 更近」两个半平面的分界线，而这正是两个沃罗诺伊单元之间的边界。

Every edge in a Voronoi diagram is, in essence, the perpendicular bisector of the segment joining two sites. To see why, recall the definition of a perpendicular bisector: it is the straight line whose every point is equidistant from the two endpoints of the segment. If we treat the two sites as the endpoints of a segment, then this perpendicular bisector is exactly the dividing line that separates the half-plane “closer to site A” from the half-plane “closer to site B,” which is precisely the boundary between two Voronoi cells.

垂直平分线有两个关键性质需要记住：第一，它经过线段的中点；第二，它垂直于这条线段。因此，如果两个站点连成的线段是水平方向，那么对应的垂直平分线就是一条竖直直线；如果线段是竖直方向，垂直平分线就是一条水平直线。这个直觉能帮你在一眼之间判断出单元边界的大致走向，也能用来快速检查计算结果是否合理。

The perpendicular bisector has two key properties to remember: first, it passes through the midpoint of the segment; second, it is perpendicular to the segment. Consequently, if the segment joining two sites is horizontal, the corresponding perpendicular bisector is a vertical line; if the segment is vertical, the bisector is a horizontal line. This intuition lets you judge the rough direction of a cell boundary at a glance, and also gives you a quick way to check whether a calculated result is sensible.

3. 用坐标求垂直平分线方程：两步法 | Finding the Perpendicular Bisector Equation from Coordinates: A Two-Step Method

当站点以坐标形式给出时，求垂直平分线方程有一个简洁的两步法。第一步，用「距离相等」建立方程：设直线上任意一点为 P(x, y)，令 P 到站点 A 的距离等于 P 到站点 B 的距离，即 PA = PB。第二步，两边平方后展开、化简，x² 和 y² 项会互相抵消，最终得到一个关于 x 和 y 的线性方程，这就是垂直平分线的方程。

When sites are given as coordinates, there is a clean two-step method for finding the perpendicular bisector’s equation. Step one is to set up an equation using “equal distances”: let any point on the line be P(x, y), and set the distance from P to site A equal to the distance from P to site B, that is PA = PB. Step two is to square both sides, expand, and simplify; the x² and y² terms cancel out, leaving a linear equation in x and y, which is precisely the equation of the perpendicular bisector.

以站点 A(0, 0) 和 B(4, 0) 为例。距离公式给出 PA² = (x − 0)² + (y − 0)² = x² + y²，而 PB² = (x − 4)² + (y − 0)² = x² − 8x + 16 + y²。令两者相等并化简：x² + y² = x² − 8x + 16 + y²，消去后得到 8x = 16，即 x = 2。这条竖直直线 x = 2 经过线段 AB 的中点 (2, 0)，并且垂直于水平的 AB，完全符合垂直平分线的两个性质。

Take sites A(0, 0) and B(4, 0) as an example. The distance formula gives PA² = (x − 0)² + (y − 0)² = x² + y², while PB² = (x − 4)² + (y − 0)² = x² − 8x + 16 + y². Setting them equal and simplifying: x² + y² = x² − 8x + 16 + y², which after cancellation gives 8x = 16, so x = 2. This vertical line x = 2 passes through the midpoint (2, 0) of segment AB and is perpendicular to the horizontal segment AB, exactly matching the two properties of a perpendicular bisector.

当站点连线不是水平或竖直时，化简后得到的方程会同时含有 x 和 y 两个变量，例如后面例题中站点 A(0, 0) 与 C(2, 4) 的垂直平分线方程为 x + 2y = 5。无论结果形式如何，检验方法都是一样的：把两个站点的中点代入方程，等式应当成立；再检查方程的斜率与两站点连线的斜率乘积是否为 −1。

When the segment joining the sites is neither horizontal nor vertical, the simplified equation will contain both x and y. For example, later in the worked example, the perpendicular bisector of sites A(0, 0) and C(2, 4) has equation x + 2y = 5. Whatever the final form, the checks are the same: substitute the midpoint of the two sites into the equation and it should hold; and verify that the product of the line’s slope and the slope of the segment joining the two sites equals −1.

4. 逐步构造沃罗诺伊图：从散点到完整划分 | Constructing a Voronoi Diagram Step by Step: From Scattered Points to a Complete Partition

对于只有三到五个站点的题目，构造沃罗诺伊图可以按一个清晰的流程进行。第一步，把全部站点标在坐标系中。第二步，为每一对「相邻」的站点画出它们之间线段的垂直平分线；「相邻」指的是这两个站点的单元会共享一条边。第三步，保留那些真正作为单元边界的平分线线段，擦掉延伸到单元之外的半直线部分，让边在顶点处终止。最后检查：每个单元内部只含一个站点，且每个顶点都由三条边汇聚而成。

For questions with only three to five sites, the Voronoi diagram can be constructed following a clear procedure. First, plot all the sites on the coordinate plane. Second, for every pair of “adjacent” sites (meaning the two sites whose cells will share an edge), draw the perpendicular bisector of the segment joining them. Third, keep only the portions of those bisectors that genuinely serve as cell boundaries, erasing the half-lines that extend beyond the cells so that edges terminate at vertices. Finally, check that each cell contains exactly one site and that each vertex is the meeting point of three edges.

一个实用的提示：你不需要画出所有站点两两之间的垂直平分线，因为很多平分线会落在图的「内部」，被其他边界截断，永远不会成为真正的边。观察站点的相对位置，先找出大致呈三角形分布的相邻站点组，再对这些组画出平分线，通常能省下大量时间。判断哪些平分线保留、哪些被截断，正是 IB 考试中作图题考察的难点。

A useful tip: you do not need to draw the perpendicular bisector between every pair of sites, because many bisectors will fall “inside” the figure and be cut off by other boundaries, never becoming real edges. Observe the relative positions of the sites, first identify groups of adjacent sites that roughly form triangles, and draw bisectors for those groups; this usually saves a great deal of time. Deciding which bisectors survive and which are truncated is exactly the difficulty tested in IB construction questions.

5. 最近邻插值：判断一个点属于哪个单元 | Nearest Neighbour Interpolation: Deciding Which Cell a Point Belongs To

「最近邻插值」（nearest neighbour interpolation）是沃罗诺伊图最直接的应用：给定一个不在边界上的查询点，要判断它属于哪个单元，只需计算它到每一个站点的距离，取距离最小的那个站点即可。IB 考题通常会给出一组坐标和一个查询点，要求考生计算出最近站点，有时还要进一步说明该点落在图的哪个区域。

Nearest neighbour interpolation is the most direct application of the Voronoi diagram: given a query point that is not on a boundary, to decide which cell it belongs to, simply calculate its distance to every site and choose the site with the smallest distance. IB questions typically give a set of coordinates plus a query point, and ask the candidate to work out the nearest site, sometimes going further to state which region of the diagram the point falls into.

这个方法的计算量不大，但必须系统：先用距离公式 d = √((x₂ − x₁)² + (y₂ − y₁)²) 逐一计算，再横向比较。由于题目只需要比较大小，实际计算时可以直接比较「距离的平方」，省去开根号，既减少计算错误又加快速度。这个技巧在考试中非常实用，因为许多考生会因开根号出错而失分。

The amount of computation is modest, but it must be systematic: first use the distance formula d = √((x₂ − x₁)² + (y₂ − y₁)²) to compute each distance in turn, then compare them. Since the question only needs a comparison of sizes, in practice you can compare the “squared distances” directly and skip the square root, which reduces arithmetic errors and saves time. This technique is highly valuable in exams, because many candidates lose marks through square-root mistakes.

6. 最大空圆问题：沃罗诺伊顶点的几何意义 | The Largest Empty Circle Problem: The Geometric Meaning of Voronoi Vertices

沃罗诺伊图还有一个精巧的几何结论，称为「最大空圆」问题：在一个区域内画一个尽可能大的圆，要求圆内不包含任何站点。可以证明，这个最大空圆的圆心要么位于某个沃罗诺伊顶点处，要么位于区域的边界上。当圆心在顶点处时，圆会恰好同时经过三个（或更多）站点，也就是说，这个顶点是那三个站点构成三角形的外心。

The Voronoi diagram also has an elegant geometric result known as the “largest empty circle” problem: draw the largest possible circle inside a region such that the circle contains no sites. It can be shown that the centre of this largest empty circle lies either at a Voronoi vertex or on the boundary of the region. When the centre lies at a vertex, the circle passes exactly through three (or more) sites simultaneously, which means the vertex is the circumcentre of the triangle formed by those three sites.

这个结论把「最大空圆」和「外接圆」联系了起来，是 IB 试卷里一道经典的融合题：给出三个站点，要求找到能放下且不碰到任何站点的最大圆的圆心和半径。解题思路就是先求出三个站点两两之间的垂直平分线，它们的交点就是外心，也就是最大空圆的圆心；半径则是这个圆心到任意一个站点的距离。这类题目把垂直平分线、三角形外心和距离公式串成了一条完整的推理链。

This result links the “largest empty circle” to the “circumcircle,” and it is a classic integrative question on IB papers: given three sites, find the centre and radius of the largest circle that can be placed without touching any site. The solution strategy is to first find the perpendicular bisectors between the three sites in pairs; their intersection is the circumcentre, which is the centre of the largest empty circle, and the radius is the distance from this centre to any one site. Questions of this type string together the perpendicular bisector, the triangle circumcentre, and the distance formula into a complete chain of reasoning.

7. 德劳内三角剖分：沃罗诺伊图的对偶图 | Delaunay Triangulation: The Dual Graph of a Voronoi Diagram

德劳内三角剖分（Delaunay triangulation）是沃罗诺伊图的「对偶图」：把共享一条边的两个沃罗诺伊单元所对应的站点用线段连接起来，得到的三角网格就是德劳内三角剖分。换句话说，沃罗诺伊图和德劳内三角剖分携带的是同一份信息，只是表达方式不同，一个描述「区域的划分」，一个描述「站点之间的连接关系」。

The Delaunay triangulation is the “dual graph” of the Voronoi diagram: connect with a segment the sites corresponding to any two Voronoi cells that share an edge, and the resulting triangular mesh is the Delaunay triangulation. In other words, the Voronoi diagram and the Delaunay triangulation carry the same information, just expressed differently: one describes the partition of space, the other describes the connectivity between sites.

德劳内三角剖分有一个著名的优良性质：它倾向于生成「尽量不细长」的三角形，使得所有三角形的最小内角尽可能大。这一性质让它在有限元分析、地形建模和三维网格生成中被广泛使用，因为形状规则的三角形能带来更稳定的数值计算。理解沃罗诺伊图与德劳内三角剖分的对偶关系，也是 IB AI 课程中关于「网络与图」主题的重要延伸。

The Delaunay triangulation has a famous favourable property: it tends to produce triangles that are “as little elongated as possible,” so that the smallest interior angle of every triangle is as large as it can be. This property makes it widely used in finite element analysis, terrain modelling, and 3D mesh generation, because regularly shaped triangles lead to more stable numerical computation. Understanding the duality between the Voronoi diagram and the Delaunay triangulation is also an important extension of the “networks and graphs” theme in the IB AI course.

8. 现实应用：从手机基站到霍乱地图 | Real-World Applications: From Mobile Phone Towers to the Cholera Map

沃罗诺伊图的魅力在于它无处不在。移动通信公司用它划分基站的覆盖范围，让每部手机自动连接到信号最强的基站；城市规划者用它确定学校或医院的「招生区」「服务区」，判断每一位居民应该去哪个最近的设施；零售和物流行业用它划分门店的配送区域，优化配送路线。任何一个「谁离我最近、我该去哪个点」的问题，都可以用沃罗诺伊图来建模。

The appeal of the Voronoi diagram is that it appears everywhere. Mobile communication companies use it to divide the coverage of base stations so that every phone automatically connects to the base station with the strongest signal; urban planners use it to define “catchment areas” for schools or hospitals and to decide which facility each resident should go to; and the retail and logistics industries use it to divide delivery territories among stores and optimise routes. Any question of the form “who is nearest to me, which point should I go to” can be modelled with a Voronoi diagram.

一个经典的历史例子是 1854 年伦敦霍乱疫情中约翰·斯诺（John Snow）的地图。他在地图上标出每一个病人的住址，并画出了围绕每个公共水泵的「泰森多边形」式区域，从而发现大多数病人都集中在宽街水泵的单元内，锁定了一个被污染的水泵，这被认为是现代流行病学与空间分析的起点。这个例子也说明，沃罗诺伊图背后的思想早在它被正式命名之前就已经在帮助人类解决问题。

A classic historical example is John Snow’s map of the 1854 London cholera outbreak. He plotted the address of every patient on a map and drew “Voronoi-like” regions around each public water pump, discovering that most of the patients clustered within the cell of the Broad Street pump, and thereby pinpointed a contaminated pump. This is regarded as the starting point of modern epidemiology and spatial analysis. The example also shows that the ideas behind the Voronoi diagram were helping people solve problems long before the diagram was formally named.

9. 完整例题：三步求出最近站点与最大空圆 | A Full Worked Example: Finding the Nearest Site and the Largest Empty Circle

下面用一个完整例题串起本节学到的所有技巧。设三个站点为 A(0, 0)、B(4, 0)、C(2, 4)，查询点 P(2, 1)。第一问：P 属于哪个站点？先算距离的平方：PA² = (2 − 0)² + (1 − 0)² = 5，PB² = (2 − 4)² + (1 − 0)² = 5，PC² = (2 − 2)² + (1 − 4)² = 9。比较可知 PB² = 5 最小，因此 P 离站点 B 最近，P 落在 B 的单元内。

Let us use one complete worked example to tie together all the techniques in this section. Take three sites A(0, 0), B(4, 0), C(2, 4) and a query point P(2, 1). First part: to which site does P belong? Compute the squared distances: PA² = (2 − 0)² + (1 − 0)² = 5, PB² = (2 − 4)² + (1 − 0)² = 5, PC² = (2 − 2)² + (1 − 4)² = 9. Comparing them, PB² = 5 is the smallest, so P is nearest to site B, and P falls inside B’s cell.

第二问：求出三条单元边界的方程。AB 的垂直平分线：令 PA² = PB²，得 x = 2。AC 的垂直平分线：令 PA² = PC²，即 x² + y² = (x − 2)² + (y − 4)²，展开化简得 x + 2y = 5。BC 的垂直平分线：令 PB² = PC²，得 y = (x + 1)/2。这三条直线就是沃罗诺伊图的全部边界。

Second part: find the equations of the three cell boundaries. The perpendicular bisector of AB: setting PA² = PB² gives x = 2. The perpendicular bisector of AC: setting PA² = PC², that is x² + y² = (x − 2)² + (y − 4)², expands and simplifies to x + 2y = 5. The perpendicular bisector of BC: setting PB² = PC² gives y = (x + 1)/2. These three lines are all the boundaries of the Voronoi diagram.

第三问：求最大空圆的圆心和半径。三条垂直平分线两两相交于同一点，解 x = 2 与 y = (x + 1)/2 得交点为 (2, 1.5)。验证它也在 x + 2y = 5 上：2 + 2(1.5) = 5，成立。所以顶点（也是外心）为 (2, 1.5)。半径等于该点到任一站点 A 的距离：√((2 − 0)² + (1.5 − 0)²) = √(4 + 2.25) = √6.25 = 2.5。因此最大空圆的圆心为 (2, 1.5)，半径为 2.5。

Third part: find the centre and radius of the largest empty circle. The three perpendicular bisectors intersect at a single point; solving x = 2 together with y = (x + 1)/2 gives the intersection (2, 1.5). Check that it also lies on x + 2y = 5: 2 + 2(1.5) = 5, which holds. So the vertex (which is also the circumcentre) is (2, 1.5). The radius equals the distance from this point to any site, say A: √((2 − 0)² + (1.5 − 0)²) = √(4 + 2.25) = √6.25 = 2.5. Therefore the largest empty circle has centre (2, 1.5) and radius 2.5.

10. 考试技巧与常见错误 | Exam Technique and Common Mistakes

考场上处理沃罗诺伊图题目，有几个习惯能显著减少失分。第一，作图题一定要用铅笔和直尺，并明确标注出中点和垂直符号，因为评分标准会看这些细节。第二，凡是求「最近站点」，先判断是否需要开根号，比较距离的平方通常更快更稳。第三，求垂直平分线方程后，务必把两站点中点代入验算，避免符号或展开错误。第四，涉及最大空圆时，先想清楚圆心在顶点还是在边界上，再决定用「三条平分线求交点」还是「点到边界的距离」。

When handling Voronoi diagram questions in the exam, a few habits can significantly reduce lost marks. First, in construction questions always use a pencil and ruler, and clearly mark the midpoints and right-angle symbols, because the mark scheme rewards these details. Second, whenever you need the “nearest site,” judge whether you actually need the square root; comparing squared distances is usually faster and more reliable. Third, after finding a perpendicular bisector equation, always substitute the midpoint of the two sites to verify it, avoiding sign or expansion errors. Fourth, for largest-empty-circle questions, decide first whether the centre lies at a vertex or on a boundary, then choose between “intersecting three bisectors” or “distance from a point to a boundary.”

最常见的错误有三个。其一是把「距离公式」和「中点公式」混淆：中点公式求的是线段中点坐标，垂直平分线虽然经过中点，但其方程要靠「到两端点距离相等」来建立，不能直接套中点公式。其二是开根号后比较大小出错，尤其是当多个距离的平方非常接近时。其三是误以为每个站点对之间都要画垂直平分线，导致图上出现大量无用的、被截断的线段。避免这三个错误，沃罗诺伊图部分的分数基本可以稳稳拿下。

There are three most common mistakes. The first is confusing the “distance formula” with the “midpoint formula”: the midpoint formula gives the coordinates of the segment’s midpoint, and although the perpendicular bisector passes through the midpoint, its equation must be built from “equal distances to the two endpoints,” not by directly applying the midpoint formula. The second is making comparison errors after taking square roots, especially when several squared distances are very close. The third is assuming that a perpendicular bisector must be drawn between every pair of sites, producing a figure full of useless, truncated segments. Avoid these three mistakes and the marks in the Voronoi diagram section are essentially guaranteed.

Summary | 总结

沃罗诺伊图把平面划分成若干个单元，使得每个单元内的点到其站点最近。它的每一条边都是两个站点间线段的垂直平分线，可以用「距离相等、两边平方、化简」的两步法求出方程。给定查询点求最近站点，就是最近邻插值，直接比较距离的平方即可。三条垂直平分线的交点是沃罗诺伊顶点，也是对应三角形的外心，它确定了不包含任何站点的最大空圆的圆心和半径。沃罗诺伊图的对偶图是德劳内三角剖分，二者共同支撑起移动通信、城市规划、物流配送与流行病学等众多现实应用。

The Voronoi diagram partitions the plane into cells so that every point in a cell is closest to that cell’s site. Each of its edges is the perpendicular bisector of the segment between two sites, and its equation can be found with the two-step method of “equal distances, square both sides, simplify.” Finding the nearest site for a query point is nearest neighbour interpolation, which can be done by comparing squared distances directly. The intersection of three perpendicular bisectors is a Voronoi vertex and also the circumcentre of the corresponding triangle; it determines the centre and radius of the largest circle that contains no sites. The dual of the Voronoi diagram is the Delaunay triangulation, and together they underpin numerous real-world applications including mobile communication, urban planning, logistics delivery, and epidemiology.

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