凸包下界（convex-hull lower bound）

很自然會問：有沒有什麼巧妙手法能算凸包，比葛立恆掃描與單調鏈的 O(n log n) 更快？凸包下界回答：不行——至少在以比較為基礎的方法、且在最壞情況下不行。它證明計算凸包的時間有一個 Omega(n log n) 的硬下限，方法是說明：若你能快速求凸包，你也就能快速排序，而排序本身用比較無法快過 n log n。

這個論證是「從排序歸約」，而且漂亮地簡單。假設你要把 n 個實數 x1, ..., xn 排序。把每個數 xi 對映到點 (xi, xi^2)，它就落在拋物線 y = x^2 上。拋物線上的每個點都是這類點集凸包的頂點（拋物線只往一個方向彎，所以沒有任何點會落在其他點內部）。現在計算這 n 個點的凸包。沿邊界依序讀出凸包的頂點，就列出依 x 座標排序的點——而那正是原數列的排序結果。所以一個凸包演算法，加上建點與讀回的 O(n) 工作，就把 n 個數排好了。既然比較排序需要 Omega(n log n)，任何以比較為基礎的凸包演算法也必然如此。

這是「用歸約證明下界」的教科書範例，並帶來兩個誠實的教訓。第一，這個下界是針對比較／代數決策樹模型；它並不禁止利用特殊結構的更快方法，例如座標是有界範圍內的整數時，桶式技巧可能勝過 n log n。第二，從 A 歸約到 B 證明的是 B 至少和 A 一樣難——這裡是求凸包至少和排序一樣難——它並不表示求凸包很容易。這個下界與葛立恆掃描和單調鏈的 O(n log n) 上界相符，所以對一般輸入，那些演算法是最佳的。