# Voronoi图和最近站点问题

> IB 数学 AI SL · IB 数学 AI SL：第三单元 几何与三角学
> 来源: https://www.owlsprep.com/zh/study/ib-math-ai-sl-u3-voronoi-diagrams-and-closest-site/

本模块讲解Voronoi图如何根据到站点的距离划分空间，如何求解最近站点问题，以及IB考试中的常见应用，包括补全部分图和最大空圆问题。

**先修:** [坐标几何：中点和距离公式](https://www.owlsprep.com/zh/study/ib-math-ai-sl-u2-coordinate-geometry-basics/); [直线方程](https://www.owlsprep.com/zh/study/ib-math-ai-sl-u1-equations-of-lines/)

## 学习目标

- 识别Voronoi图的关键组成部分
- 为Voronoi边构造垂直平分线
- 求解任意给定点的最近站点问题
- 应用Voronoi图解决最大空圆问题

## 1. 核心定义与基本性质

**Voronoi图** — Voronoi图根据到一组称为站点的点的距离，将平面划分为多个区域（单元）。每个单元内的任意点都比其他站点更靠近该单元的站点。

*例:* 医院分布图中，每个区域显示任意地址最近的医院。

Voronoi图的每条边都是连接两个站点的线段的垂直平分线的一段。Voronoi顶点是三条边的交点，到三个相邻站点的距离相等。

**例题:** 三个站点分别在A(1, 3)、B(3, 5)和C(5, 3)。验证点(3, 3)到所有三个站点的距离相等。

1. 回忆两点$(x_1,y_1)$和$(x_2,y_2)$之间的距离公式：
2. $$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$
3. 计算(3,3)到A(1,3)的距离：
4. $$d_A = \sqrt{(3-1)^2 + (3-3)^2} = \sqrt{2^2 + 0^2} = 2$$
5. 计算(3,3)到B(3,5)的距离：
6. $$d_B = \sqrt{(3-3)^2 + (3-5)^2} = \sqrt{0^2 + (-2)^2} = 2$$
7. 计算(3,3)到C(5,3)的距离：
8. $$d_C = \sqrt{(3-5)^2 + (3-3)^2} = \sqrt{(-2)^2 + 0^2} = 2$$
9. 所有距离都相等，因此(3,3)确实到三个站点距离相等。

> **考试提示:** Voronoi顶点总是到三个站点距离相等——这是考试中常见的考点。

## 2. 求解最近站点问题

要找到距离给定测试点最近的站点，你可以利用已有图判断测试点位于哪个单元，或者计算测试点到每个站点的距离后比较大小。位于Voronoi边上的点到两个相邻站点距离相等。

**最近站点问题** — 判断平面内任意给定点距离哪个预先存在的站点最近的问题。常见应用包括寻找最近的应急服务或零售门店。

**例题:** 两个站点分别在S₁(0, 0)和S₂(4, 0)。哪个站点距离点P(1, 2)更近？

1. 计算P到S₁的距离：
2. $$d_1 = \sqrt{(1-0)^2 + (2-0)^2} = \sqrt{1 + 4} = \sqrt{5} \approx 2.24$$
3. 计算P到S₂的距离：
4. $$d_2 = \sqrt{(1-4)^2 + (2-0)^2} = \sqrt{9 + 4} = \sqrt{13} \approx 3.61$$
5. 比较距离：$d_1 < d_2$，因此S₁是最近的站点。

> **tip**
>
> 如果点恰好位于Voronoi边上，那么它到两个相邻站点距离相等——这种情况下考试接受任意一个答案。

## 3. 构造Voronoi边

要找到两个站点之间的Voronoi边，你需要计算连接两个站点线段的垂直平分线，步骤如下：
1. 计算两个站点的中点
2. 计算连接两个站点线段的斜率
3. 求垂直平分线的斜率，即原斜率的负倒数
4. 写出垂直平分线的完整方程

**例题:** 求站点A(2, 4)和B(6, 2)之间垂直平分线（Voronoi边）的方程。

1. 计算AB的中点M：
2. $$M = \left(\frac{2+6}{2}, \frac{4+2}{2}\right) = (4, 3)$$
3. 计算线段AB的斜率：
4. $$m_{AB} = \frac{2 - 4}{6 - 2} = \frac{-2}{4} = -\frac{1}{2}$$
5. 求垂直平分线的斜率（负倒数）：
6. $$m_{\perp} = 2$$
7. 将中点(4,3)代入$y = mx + c$求y截距：
8. $$3 = 2(4) + c \implies c = -5$$
9. Voronoi边的最终方程：
10. $$y = 2x - 5$$

**概念自测**

测试你的理解：

1. 点(0, 2)和(4, 6)的中点是？

   - (2, 4)
   - (4, 2)
   - (2, 2)
   - (4, 4)

   *答案:* (2, 4)

   *解析:* 正确！中点是x坐标的平均值和y坐标的平均值。

## 4. 最大空圆问题

最大空圆问题是Voronoi图的常见优化应用。它要求找到新站点的最优位置，使得新站点尽可能远离所有现有站点。最大空圆的圆心一定是Voronoi顶点，因为这些点是距离所有现有站点最远的点。

**最大空圆问题** — 一种优化问题，寻找新站点的位置，使得新站点到所有现有站点的最小距离最大。

**例题:** 三个现有消防站分别在A(1, 3)、B(3, 5)、C(5, 3)。唯一的Voronoi顶点在(3, 3)，到每个消防站的距离都是2个单位。找新消防站的最优位置，要求新站尽可能远离所有现有消防站。

1. 回忆新站的最优位置是Voronoi顶点，即距离所有现有站点最远的点。
2. 本例中的Voronoi顶点是(3, 3)，到最近现有消防站的最小距离是2个单位。
3. 结论：最优位置是$(3, 3)$。

> **info**
>
> 考试中通常会给出所有候选Voronoi顶点，你只需要计算每个顶点的距离并选择最大值即可。

> **考试提示:** 一定要检查题目是否给出了有界区域：最大圆的圆心可能在区域边界上，而不只是在内部顶点。

## 常见错误

- **错误做法:** 使用原站点间线段的斜率，而不是负倒数
  - 原因: 这样得到的是平行线，不是垂直平分线，因此Voronoi边错误
  - 正确做法: 记住互相垂直的斜率乘积为-1，因此一定要取负倒数
- **错误做法:** 忘记检查有界区域中最大空圆的边界点
  - 原因: 如果边界距离所有站点都很远，最大圆的圆心会在边界上，而不是内部顶点
  - 正确做法: 一定要检查所有候选点，包括给定区域的边界点
- **错误做法:** 声称Voronoi顶点只到两个站点距离相等
  - 原因: 顶点是三条边的交点，因此到三个站点距离相等，不是两个
  - 正确做法: 记住：边到两个站点距离相等，顶点到三个站点距离相等
- **错误做法:** 比较最近站点时计算平方距离出错
  - 原因: 比较平方距离可以节省时间，但计算错误会导致结果错误
  - 正确做法: 反复检查你的计算，或者使用实际距离（开平方）来确认

## 速查表

| 概念 | 核心结论 |
| --- | --- |
| Voronoi单元 | 所有点都比其他站点更靠近一个站点 |
| Voronoi边 | 垂直平分线，到两个站点距离相等 |
| Voronoi顶点 | 三条边的交点，到三个站点距离相等 |
| 最近站点问题 | 比较距离或判断点所在的单元 |
| 垂直平分线 | 中点 + 负倒数斜率 |
| 最大空圆 | 圆心在Voronoi顶点，最大化最小距离 |

## 下一步

Voronoi图是IB AI SL中重要的应用几何主题，经常和其他优化、实际问题解决题目一起在Paper 2中考查。掌握这个子主题后，你可以继续学习更高级的优化问题，比如线性规划，它需要类似的坐标几何和批判性思维技能。你也可以复习核心先修概念，比如中点、距离、垂直线，来巩固你的理解，因为这些是所有Voronoi图问题的基础。巩固这些技能能帮助你应对这个主题的所有考试题目。

- [非直角三角形的面积公式](https://www.owlsprep.com/zh/study/ib-math-ai-sl-u3-triangle-area-formula-for-non/)
- [统计与概率](https://www.owlsprep.com/zh/study/ib-math-ai-sl-u4-overview/)
- [离散型与连续型数据类型](https://www.owlsprep.com/zh/study/ib-math-ai-sl-u4-discrete-and-continuous-data-types/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/ib-math-ai-sl-u3-voronoi-diagrams-and-closest-site/