Voronoi 圖
Voronoi 圖（Voronoi diagram）把平面分成好幾個區域，每個區域內的所有點都離同一個「站點」最近。它能回答「哪一家醫院離我最近」「這個位置的降雨量該用哪個氣象站估計」「垃圾場該蓋在哪裡才能離所有住家最遠」這類問題。Voronoi 圖是 IB Math AI 獨有的主題，屬於 SL 與 HL 共同內容（課綱 3.5、3.6）。
垂直平分線
線段 \(AB\) 的垂直平分線（perpendicular bisector）上的每一點，到 \(A\) 和到 \(B\) 的距離都相等。它是 Voronoi 圖的基本零件。
求 \(A(x_1, y_1)\)、\(B(x_2, y_2)\) 垂直平分線的三步驟：
- 求中點 \(M = \left(\dfrac{x_1 + x_2}{2}, \dfrac{y_1 + y_2}{2}\right)\)。
- 求 \(AB\) 的斜率 \(m\)，垂直平分線斜率為 \(-\dfrac{1}{m}\)。
- 用點斜式寫出通過 \(M\) 的直線。
Voronoi 圖的組成
| 名稱 | 英文 | 意義 |
|---|---|---|
| 站點 | site | 給定的點，例如醫院、氣象站、手機基地台 |
| 區域 | cell | 離某個站點最近的所有點構成的區域 |
| 邊 | edge | 兩個區域的交界，是兩個站點連線的垂直平分線的一部分 |
| 頂點 | vertex | 三個（或以上）區域相交的點，到這三個站點的距離相等 |
頂點的性質
Voronoi 頂點到相鄰三個站點的距離都相等，也就是這三個站點所成三角形的外心。求頂點時，只要解兩條垂直平分線的交點。
新增一個站點
考試常給一張不完整的 Voronoi 圖，要你加入新站點後更新：
- 找出新站點落在哪一個區域內。
- 畫新站點與該區域站點的垂直平分線，切掉離新站點較近的部分。
- 對相鄰區域重複，直到新區域封閉。
- 擦掉被新區域吃掉的舊邊。
Voronoi 圖的應用
最近鄰內插法
最近鄰內插法（nearest neighbour interpolation）：要估計某位置的數值（例如雨量），就直接採用該位置所在區域站點的數值。
垃圾場問題（toxic waste dump problem）
要在某範圍內找一個點，讓它離最近的站點盡量遠。答案一定出現在下列候選點之一：
- Voronoi 圖的頂點；
- Voronoi 的邊與範圍邊界的交點；
- 範圍的角落。
逐一計算每個候選點到最近站點的距離，取最大的那一個。
推薦影音
Voronoi 圖入門
簡述：Mr. Flynn IB 用直觀的動畫介紹站點、區域、邊與頂點，並說明為何 Voronoi 邊是垂直平分線，適合第一次學習。
Voronoi 圖完整講解與考題
簡述：Revision Village 示範垂直平分線方程式、新增站點與垃圾場問題，涵蓋本頁所有題型。
練習題
以下練習使用三個站點：\(A(0, 0)\)、\(B(4, 0)\)、\(C(0, 6)\)。
練習 1
求 \(A(2, 4)\) 與 \(B(6, 0)\) 的垂直平分線方程式（這題的 \(A\)、\(B\) 與上面的站點無關）。
參考解答
中點 \((4, 2)\)；\(AB\) 斜率 \(= \dfrac{0 - 4}{6 - 2} = -1\)，垂直斜率 \(= 1\)。
\(y - 2 = 1(x - 4)\)，即 \(y = x - 2\)。
練習 2
求站點 \(A(0, 0)\)、\(B(4, 0)\)、\(C(0, 6)\) 的 Voronoi 頂點，並驗證它到三個站點等距。
參考解答
\(AB\) 的垂直平分線是 \(x = 2\)；\(AC\) 的垂直平分線是 \(y = 3\)。交點 \(V(2, 3)\)。
\(VA = VB = VC = \sqrt{4 + 9} = \sqrt{13} \approx 3.61\)。
練習 3
用最近鄰內插法，點 \(P(3, 1)\) 的數值應採用哪一個站點的資料？
參考解答
\(PA = \sqrt{10} \approx 3.16\)、\(PB = \sqrt{2} \approx 1.41\)、\(PC = \sqrt{9 + 25} \approx 5.83\)。\(P\) 離 \(B\) 最近，採用 \(B\) 的資料。
練習 4
在範圍 \(0 \le x \le 4\)、\(0 \le y \le 6\) 內，要找一個點離最近站點最遠（垃圾場問題）。
(a) 求 \(BC\) 的垂直平分線方程式。 (b) 它與邊界 \(x = 4\) 交於哪一點？ (c) 比較頂點 \(V(2, 3)\)、角落 \((4, 6)\) 與 (b) 的點，哪個位置最好？
參考解答
(a) \(BC\) 中點 \((2, 3)\)，斜率 \(\dfrac{6 - 0}{0 - 4} = -\dfrac{3}{2}\)，垂直斜率 \(\dfrac{2}{3}\)：\(y = \dfrac{2}{3}x + \dfrac{5}{3}\)。
(b) \(x = 4\) 時 \(y = \dfrac{13}{3} \approx 4.33\)，交點 \(Q\left(4, \dfrac{13}{3}\right)\)。
(c) 各點到最近站點的距離：
- \(V(2, 3)\)：\(\sqrt{13} \approx 3.61\)
- 角落 \((4, 6)\)：最近的是 \(C\)，距離 \(4\)
- \(Q(4, 4.33)\)：到 \(B\) 與 \(C\) 都是 \(\dfrac{13}{3} \approx 4.33\)
最佳位置是 \(Q\left(4, \dfrac{13}{3}\right)\)。這題說明答案不一定在 Voronoi 頂點，邊界交點也要檢查。