学习指南

Voronoi图和最近站点问题

IB 数学 AI SL· Unit 3: Geometry and Trigonometry, Topic 6· 15 分钟阅读

1. 1. 核心定义与基本性质★★☆☆☆⏱ 5 min

📘 定义

Voronoi图

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

例:

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

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

📐 例题

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

  1. 1

    回忆两点和之间的距离公式：

  2. 2
    d=(x2−x1)2+(y2−y1)2d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}
  3. 3

    计算(3,3)到A(1,3)的距离：

  4. 4
    dA=(3−1)2+(3−3)2=22+02=2d_A = \sqrt{(3-1)^2 + (3-3)^2} = \sqrt{2^2 + 0^2} = 2
  5. 5

    计算(3,3)到B(3,5)的距离：

  6. 6
    dB=(3−3)2+(3−5)2=02+(−2)2=2d_B = \sqrt{(3-3)^2 + (3-5)^2} = \sqrt{0^2 + (-2)^2} = 2
  7. 7

    计算(3,3)到C(5,3)的距离：

  8. 8
    dC=(3−5)2+(3−3)2=(−2)2+02=2d_C = \sqrt{(3-5)^2 + (3-3)^2} = \sqrt{(-2)^2 + 0^2} = 2
  9. 9

    所有距离都相等，因此(3,3)确实到三个站点距离相等。

Exam tip:

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

2. 2. 求解最近站点问题★★☆☆☆⏱ 4 min

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

📘 定义

最近站点问题

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

📐 例题

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

  1. 1

    计算P到S₁的距离：

  2. 2
    d1=(1−0)2+(2−0)2=1+4=5≈2.24d_1 = \sqrt{(1-0)^2 + (2-0)^2} = \sqrt{1 + 4} = \sqrt{5} \approx 2.24
  3. 3

    计算P到S₂的距离：

  4. 4
    d2=(1−4)2+(2−0)2=9+4=13≈3.61d_2 = \sqrt{(1-4)^2 + (2-0)^2} = \sqrt{9 + 4} = \sqrt{13} \approx 3.61
  5. 5

    比较距离：，因此S₁是最近的站点。

3. 3. 构造Voronoi边★★★☆☆⏱ 6 min

要找到两个站点之间的Voronoi边，你需要计算连接两个站点线段的垂直平分线，步骤如下：

  1. 计算两个站点的中点
  2. 计算连接两个站点线段的斜率
  3. 求垂直平分线的斜率，即原斜率的负倒数
  4. 写出垂直平分线的完整方程

📐 例题

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

  1. 1

    计算AB的中点M：

  2. 2
    M=(2+62,4+22)=(4,3)M = \left(\frac{2+6}{2}, \frac{4+2}{2}\right) = (4, 3)
  3. 3

    计算线段AB的斜率：

  4. 4
    mAB=2−46−2=−24=−12m_{AB} = \frac{2 - 4}{6 - 2} = \frac{-2}{4} = -\frac{1}{2}
  5. 5

    求垂直平分线的斜率（负倒数）：

  6. 6
    m⊥=2m_{\perp} = 2
  7. 7

    将中点(4,3)代入求y截距：

  8. 8
    3=2(4)+c  ⟹  c=−53 = 2(4) + c \implies c = -5
  9. 9

    Voronoi边的最终方程：

  10. 10
    y=2x−5y = 2x - 5
✓ 快速检测

测试你的理解：

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

    • (2, 4)

    • (4, 2)

    • (2, 2)

    • (4, 4)

4. 4. 最大空圆问题★★★☆☆⏱ 5 min

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

📘 定义

最大空圆问题

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

📐 例题

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

  1. 1

    回忆新站的最优位置是Voronoi顶点，即距离所有现有站点最远的点。

  2. 2

    本例中的Voronoi顶点是(3, 3)，到最近现有消防站的最小距离是2个单位。

  3. 3

    结论：最优位置是。

Exam tip:

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

5. 常见陷阱

错误做法:

使用原站点间线段的斜率，而不是负倒数

原因:

这样得到的是平行线，不是垂直平分线，因此Voronoi边错误

正确做法:

记住互相垂直的斜率乘积为-1，因此一定要取负倒数

错误做法:

忘记检查有界区域中最大空圆的边界点

原因:

如果边界距离所有站点都很远，最大圆的圆心会在边界上，而不是内部顶点

正确做法:

一定要检查所有候选点，包括给定区域的边界点

错误做法:

声称Voronoi顶点只到两个站点距离相等

原因:

顶点是三条边的交点，因此到三个站点距离相等，不是两个

正确做法:

记住：边到两个站点距离相等，顶点到三个站点距离相等

错误做法:

比较最近站点时计算平方距离出错

原因:

比较平方距离可以节省时间，但计算错误会导致结果错误

正确做法:

反复检查你的计算，或者使用实际距离（开平方）来确认

6. 速查表

概念

核心结论

Voronoi单元

所有点都比其他站点更靠近一个站点

Voronoi边

垂直平分线，到两个站点距离相等

Voronoi顶点

三条边的交点，到三个站点距离相等

最近站点问题

比较距离或判断点所在的单元

垂直平分线

中点 + 负倒数斜率

最大空圆

圆心在Voronoi顶点，最大化最小距离

7. 常见问题

我需要从头开始构造完整的Voronoi图吗？

不需要，IB AI SL考试通常会给出不完整的图让你补全，或者要求你在已有的完整图上解题。

最大空圆问题有什么用途？

它用于寻找新设施（医院、商店、消防站）的最优位置，使得新设施尽可能远离现有设施，以最大化可达性。

真题中的出现

AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。

  • 2023 · 2

    最大空圆优化问题

  • 2022 · 1

    找出距离点最近的站点

  • 2021 · 2

    补全不完整的Voronoi图

深入阅读

下一步

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