凸包（convex hull）

在一塊板上散落一把釘子，套上橡皮筋：它會繃到最外圍的釘子，用最小的緊繃環圈住所有東西。凸包就是那條橡皮筋的 n 維版本。給定任一點集 S，它的凸包 conv(S) 是包含 S 的最小凸集——你能在這些點外收緊的最緊凸皮。在平面上它是穿過外圍點的凸多邊形；在空間中是凸多胞形；對光滑的點雲它可以是彎曲的凸體。

有兩個等價的定義，一個由外、一個由內。由外看，conv(S) 是所有包含 S 的凸集之交集（凸集相交仍是凸的，故此交集是包含 S 的最小凸集）。由內看，conv(S) 是 S 中各點所有凸組合之集合：所有有限和 t_1*x_1 + ... + t_m*x_m，其中每個 x_i 屬於 S、每個 t_i >= 0、且權重之和為 1。凸組合不過是加權平均，是權重非負的重心，所以凸包就是你能用有限多個樣本點作為平衡點所能達到的一切。

凸包無處不在：它定義線性規劃的可行域、機率分佈均值的支撐、多項式的牛頓多胞形，以及計算幾何中的基本形狀。卡拉特奧多里定理銳化了「由內」的圖像——在 R^n 中每個凸組合至多只需 n + 1 個點——這正是為何有限集的凸包是頂點有限的多胞形。一個提醒：閉集的凸包不必是閉的（想像一個閉集，其點以某種方式奔向無窮，只在極限中填滿一個半平面），所以對無界的 S 常取閉凸包，即 conv(S) 的閉包。