喬登多邊形定理

喬登多邊形定理（Jordan polygon theorem）是一個描述任意（簡單）多邊形均會將歐氏平面分為兩塊區域的定理。本文簡述此定理的證明。

1　術語

以下對任意非負整數 $n \comma$我們記 $[n] = \{0 \cm 1 \cm \ldots \cm n\varminus1\} \period$

1.1　線段

對任意 $p, q \in \RR^2 \comma$我們用 \[\begin{split}[p, q] = \bigl\{(1 - t)p + tq : 0 \leq t \leq 1\bigr\}\end{split}\] 代表連接 $p$ 與 $q$ 的線段。

1.2　折線段

設 $P \subseteq \RR^2 \period$若存在非負整數 $n$ 與相異的 $p_0 \cm p_1 \cm \ldots \cm p_n \in \RR^2$ 滿足 \[\begin{split} P = \bigcup_{i=0}^{n-1} [p_i, p_{i+1}] \comma \end{split}\] 且對任意相異的 $i, j \in \{0 \cm 1 \cm \ldots \cm n \varminus 1\}$ 均有 \[\begin{split} [p_i, p_{i+1}] \cap [p_j, p_{j+1}] \subseteq \{p_i, p_{i+1}\} \cap \{p_j, p_{j+1}\} \comma \end{split}\] 則我們稱 $P$ 為一條連接 $p_0$ 與 $p_n$ 的折線段。此時我們稱點列 $(p_0 \cm p_1 \cm \ldots \cm p_n)$ 構成折線段 $P \period$

1.3　多邊形

設 $C \subseteq \RR^2 \period$若存在整數 $n \geq 3$ 與相異的 $p_0 \cm p_1 \cm \ldots \cm p_{n-1} \in \RR^2$ 滿足 \[\begin{split} C = [p_{n-1}, p_0] \cup \bigcup_{i=0}^{n-2} [p_i, p_{i+1}] \comma \end{split}\] 且對任意相異的 $i, j \in \{0 \cm 1 \cm \ldots \cm n \varminus 2\}$ 均有 \[\begin{split} [p_i, p_{i+1}] \cap [p_j, p_{j+1}] &\subseteq \{p_i, p_{i+1}\} \cap \{p_j, p_{j+1}\} \jcomma \\[0.6ex] [p_i, p_{i+1}] \cap [p_{n-1}, p_0] &\subseteq \{p_i, p_{i+1}\} \cap \{p_{n-1}, p_0\} \comma \end{split}\] 則我們稱 $C$ 為一多邊形。此時我們稱點列 $(p_0 \cm p_1 \cm \ldots \cm p_{n-1} \cm p_0)$ 構成多邊形 $C \period$

範例 1　設 \[\begin{split} p_0 = \mkern15mu\begin{pmatrix*}[r] 1 \\ 0\end{pmatrix*} \comma \quad p_1 = \mkern15mu\begin{pmatrix*}[r] 0 \\ 1\end{pmatrix*} \comma \\[2ex] p_2 = \begin{pmatrix*}[r]-1 \\ 0\end{pmatrix*} \comma \quad p_3 = \begin{pmatrix*}[r] 0 \\ -1\end{pmatrix*} \period \end{split}\]

1. 由於 \[\begin{split}[p_0, p_1] \cap [p_2, p_3] = \varnothing = [p_3, p_0] \cap [p_1, p_2] \comma\end{split}\]故 $(p_0, p_1, p_2, p_3, p_0)$ 能構成一多邊形。
2. 由於 \[\begin{split}\begin{pmatrix}0 \\ 0\end{pmatrix} \in [p_0, p_2] \cap [p_1, p_3]\end{split}\]且 $\{p_0, p_2\} \cap \{p_1, p_3\} = \varnothing \comma$故 $(p_0, p_2, p_1, p_3, p_0)$ 不構成多邊形。

1.4　區域

設 $D \subseteq \RR^2$。

對任意 $p, q \in D$，若存在連接 $p$ 與 $q$ 的折線段 $P \subseteq D \comma$則我們稱 $p$ 與 $q$ 在 $D$ 中連通。

此時在 $D$ 中的連通關係為一等價關係，我們稱由此關係所構成之等價類為 $D$ 中的區域。若 $D$ 恰具有 1 區域，則稱 $D$ 為連通。

範例 2　設 \[\begin{split}D = \biggl\{\begin{pmatrix}x \\ y\end{pmatrix} \in \RR^2: x \neq 0\biggr\} \comma\end{split}\] 則 $D$ 具有 2 個區域 $D_0$ 與 $D_1 \comma$其中 \[\begin{split} D_0 &= \biggl\{\begin{pmatrix}x \\ y\end{pmatrix} \in \RR^2: x > 0\biggr\} \comma \\[2.5ex] D_1 &= \biggl\{\begin{pmatrix}x \\ y\end{pmatrix} \in \RR^2: x < 0\biggr\} \period \end{split}\]

2　喬登多邊形定理

設 $C$ 是由點列 $(p_0 \cm p_1 \cm \ldots \cm p_{n-1}, p_0)$ 所構成的多邊形，其中 $n \geq 3$ 且 $p_0 \cm p_1 \cm \ldots \cm p_{n-1} \in \RR^2$ 均相異。

以下對任意 $i \in [n] \comma$我們記 \[\begin{split} i^+ &= (i + 1) \bmod n \comma \\ i^- &= (i - 1) \bmod n \comma \end{split}\] 並設 $S_i = [p_i, p_{i^+}\mkern-2mu] \period$

對任意 $q \in \RR^2$ 與任意 $i \in [n] \comma$我們定義 \[\begin{split}d(q, S_i) = \min \bigl\{\lVert q - s \rVert : s \in S_i\bigr\} \period\end{split}\] 我們設 \[\begin{split}\delta(C) = \min \bigl\{d(p_i, S_j) : i, j \in [n]\ \textrm{且}\ p_i \notin S_j \bigr\} \period\end{split}\] 此時對任意滿足 $S_i \cap S_j = \varnothing$ 的 $i, j \in [n]$ 均有 \[\begin{split}\min \bigl\{\lVert s - s\.' \rVert : (s, s\.') \in S_i \times S_j \bigr\} \leq \delta(C) \period\end{split}\]

2.1　區域數不小於 2

設 \[\begin{split}e_0 = \begin{pmatrix} x \\ y \end{pmatrix} \in \RR^2\end{split}\] 滿足 $x^2 + y^2 = 1 \comma$使得對任意相異的 $i, j \in [n]$ 與任意實數 $k \comma$均有 $p_i - p_j \neq ke_0 \period$設 \[\begin{split}e_1 = \begin{pmatrix} -y \\ x \end{pmatrix} \period\end{split}\] 此時 $\{e_0, e_1\}$ 是 $\RR^2$ 的一組單位正交基底。

對任意 $i \in [n] \comma$我們設 \[\begin{split} s_i^+ &\in \argmax_{s\.\in\.S_i}\,\langle s, e_1 \rangle \comma \\ s_i^- &\in \argmin_{s\.\in\.S_i}\,\langle s, e_1 \rangle \comma \\ \end{split}\] 並設 $S_i^* = S_i \setminus \bigl\{s_i^+\mkern-2mu\bigr\} \period$

對任意 $q \in \RR^2 \setminus C$ 與 $i \in [n] \comma$若存在實數 $k > 0$ 使 $q+ke_0 \in S_i^* \comma$則我們設 $r_i(q) = 1 \semicolon$否則設 $r_i(q) = 0 \period$設 \[\begin{split} r(q) = \sum_{i=0}^{n-1} r_i(q) \period \end{split}\]

定理 1　若 $q, q' \in \RR^2$ 相異且 $[q, q'] \cap C = \varnothing \comma$則 $r(q) - r(q')$ 為偶數。

證明　不失一般性，設 $\langle q, e_1 \rangle \leq \langle q', e_1 \rangle \period$

若 $\langle q, e_1 \rangle = \langle q', e_1 \rangle \comma$則我們有 $r(q) = r(q') \period$因此以下我們考慮 $\langle q, e_1 \rangle < \langle q', e_1 \rangle$ 的狀況即可。設 $Q$ 為能找到 $i \in [n]$ 與正實數 $k$ 使 $s + ke_0 = p_i$ 成立的 $s \in [q,q']$ 所構成的集合。我們設 $Q \cup \{q, q'\} = \{q_0, q_1, \ldots, q_{k+1}\} \comma$其中 $(q_0, q_{k+1}) = (q, q') \comma$且 \[\begin{split}\langle q_0, e_1 \rangle < \langle q_1, e_1 \rangle < \cdots < \langle q_{k+1}, e_1 \rangle \period\end{split}\] 我們說明對任意 $j \in \{0 \cm 1 \cm \ldots \cm k\} \comma$$r(q_{\.j}) - r(q_{\.j+1})$ 均為偶數。對任意 $i \in [n] \comma$$r_i(q_{\.j}) \neq r_i(q_{\.j+1})$ 成立的充要條件為存在正實數 $k$ 使得 \[\begin{split}q_{\.j+1} + ke_0 \in \bigl\{s_i^-, s_i^+\bigr\} \period\end{split}\] 由於滿足上述條件的 $i \in [n]$ 的個數只可能為 0 或 2，故 $r(q_{\.j}) - r(q_{\.j+1})$ 為偶數。至此定理得$\textrm{證。}\mkern6mu\blacksquare$

定理 2　存在相異的 $q, q' \in \RR^2 \setminus C$ 使 $r(q) - r(q') = 1 \period$

證明　設 \[\begin{split} \rod{4}{0}p &= \frac{p_0 + p_1}{2} \comma \\[1.5ex] q &= p - \frac{\delta(C)}{2}e_0 \comma \\[1.5ex] q' &= p + \frac{\delta(C)}{2}e_0 \period \end{split}\] 此時 $r(q) - r(q') = 1 \comma$故定理得$\textrm{證。}\mkern6mu\blacksquare$

定理 3（區域不小於 2） $\RR^2 \setminus C$ 的區域數不小於 2。

證明　由定理 1 與定理 2 得$\textrm{證。}\mkern6mu\blacksquare$

2.2　區域數不大於 2

對任意 $i \in [n] \comma$設 \[\begin{split} v_i = \frac{p_{i^+\mkern-2mu} - p_i}{\lVert p_{i^+\mkern-2mu} - p_i \rVert} \comma \end{split}\] 並設 $\alpha_i \in (0, 2\pi)$ 滿足 \[\begin{split} \begin{pmatrix*}[r]\cos\alpha_i & -\sin\alpha_i \\ \sin\alpha_i & \cos\alpha_i\end{pmatrix*}(-v_{i^-}) = v_i \period \end{split}\] 設 \[\begin{split}\rod{4}{0}\sigma = \min\,\biggl\{\sin \frac{\alpha_i}{2}: i \in [n]\biggr\} \period\end{split}\]

對任意 $0 < \epsilon < \delta(C)/(2\sigma) \comma$我們定義多邊形 $C^+(\epsilon)$ 與 $C^-(\epsilon)$ 如下：

• (1)對每個 $i \in [n] \comma$定義 \[\begin{split} \gdef\halphai{\alpha_{\mkern-.5mui}/2} \rod{4}{0}u_i &= \begin{pmatrix*}[r]\cos(\halphai) & -\sin(\halphai) \\ \sin(\halphai) & \cos(\halphai)\end{pmatrix*}\frac{p_{i^-}\mkern-2mu-p_i}{\lVert p_{i^-}\mkern-2mu-p_i \rVert} \comma \end{split}\] 並設 \[\begin{split} \rod{4}{0}q_i^+(\epsilon) &= p_i + \frac{\epsilon}{\sin(\halphai)}u_i \comma \\ \rod{4}{0}q_i^-(\epsilon) &= p_i + \frac{\epsilon}{\sin(\halphai)}u_i \period \end{split}\]

• (2)設 $C^+(\epsilon)$ 與 $C^-(\epsilon)$ 分別為由點列 \[\begin{split} (q_0^+(\epsilon) \cm q_1^+(\epsilon) \cm \ldots \cm q_{n-1}^+(\epsilon) \cm q_0^+(\epsilon)) \end{split}\] 與 \[\begin{split} (q_0^-(\epsilon) \cm q_1^-(\epsilon) \cm \ldots \cm q_{n-1}^-(\epsilon) \cm q_0^-(\epsilon)) \end{split}\] 所構成的多邊形。

可知對任意 $0 < \epsilon < \delta(C)/(2\sigma) \comma$有 \[\begin{split}C^+(\epsilon) \cap C = \varnothing = C^-(\epsilon) \cap C \period\end{split}\]

定理 4（區域不大於 2） $\RR^2 \setminus C$ 的區域數不大於 2。

證明　對任意 $q \in \RR^2 \setminus C \comma$設 \[\begin{split}d(q, C) = \min\,\{\lVert p-q \rVert : p \in C\} \comma\end{split}\] 則對任意 \[\begin{split}0 < \epsilon < \min\,\bigl\{d(q, C),\delta(C)\bigr\}/(2\sigma) \comma\end{split}\]我們均能找到滿足 $[s, q] \cap C = \varnothing$ 的 $s \in C^+(\epsilon) \cup C^-(\epsilon) \comma$此時 $s$ 與 $q$ 在 $\RR^2 \setminus C$ 上連通。因此若我們設 \[\begin{split}s^+ \in C^+(\delta(C)/(2\sigma)) \comma \\[0.5ex] s^- \in C^-(\delta(C)/(2\sigma)) \comma\end{split}\] 則 $\RR^2 \setminus C$ 中的點必定與 $s^+$ 或 $s^-$ 連通，即 $\RR^2 \setminus C$ 最多具有 2 個區域，故定理得$\textrm{證。}\mkern6mu\blacksquare$

2.3　區域數等於 2

定理 5（喬登多邊形定理） $\RR^2 \setminus C$ 具有 2 個區域。

證明　由定理 3 與定理 4 得$\textrm{證。}\mkern6mu\blacksquare$

參考資料