凸幾何與離散幾何

赫利定理(Helly's theorem)

/ HEL-ee /

你有一大堆凸形狀,想知道它們是否共有一點。一次檢查整堆很難。赫利定理在 n 維給出驚人的捷徑:你只需檢查其中任意 n + 1 個是否有共同點。若每個 n + 1 個的小組都重疊,那麼神奇地,所有形狀同時重疊。小子族間的局部一致,逼出全域一致。

精確地說,設 C_1, ..., C_m 是 R^n 中的凸集、m >= n + 1。赫利定理斷言:若這些集合中任意 n + 1 個有非空的共同交集,則全部 m 個有非空的共同交集。(對無窮多個集合,只要集合為緊以提供有限交性質的緊性論證,同樣成立。)在平面上(n = 2)魔法數是 3:若你的凸集任意三個都相交,則它們全都相交。證明仰賴拉東定理——把 n + 2 個點分成凸包相交的兩組——應用於巧選的見證點,是個優雅的歸納。

赫利定理是組合凸性的基石,並孕育出幾何、最佳化、甚至資料科學中一整門「赫利型」結果的產業。它解釋了為何許多可行性問題化約為檢查小的子系統,支撐中心點與火腿三明治型定理,並乾淨地證明,例如一族直線上兩兩重疊的區間必共有一點(n = 1 情形)。兩個誠實的提醒。其一,凸性不可少:對非凸集定理徹底失效——三個新月可以兩兩重疊卻無共同點。其二,數字 n + 1 恰好正確、不可再降;在平面上「任意兩個相交」不逼出共同點(圍著小孔的三個細長三角形兩兩相交卻一無所共)。

在直線上(n = 1)赫利數是 2。取任一族區間,使其中任意兩個都重疊;赫利說它們全都共有一點。具體地,區間 [0,3]、[1,4]、[2,5] 兩兩重疊,而 [2,3] 確實是三者共有。定理保證這非巧合:區間的兩兩重疊總逼出全域共同點——一旦容許像「兩段不相交線段」這種非凸集,這就失效。

在直線上,兩兩重疊的區間總共有一點(赫利,n=1)。

門檻 n + 1 不能降低,凸性不能去掉。兩者都是緊的:平面上三個細三角形可以圍著一個孔兩兩相交而三重交集為空,而任何非凸的例子即使兩兩完全重疊也會破壞結論。

又称
Helly's intersection theorem赫利交集定理