安德魯單調鏈（Andrew's monotone chain）

安德魯單調鏈（Andrew's monotone chain）是一個 O(n log n) 的凸包演算法，許多人寧可用它而非葛立恆掃描，因為它把麻煩的極角排序換成單純的依座標排序。畫面是這樣：把所有點攤開，由左到右排序（先依 x，平手依 y）。接著由左掃到右建出凸包的下緣，再掃回來建出上緣，最後把兩條鏈黏成一個迴圈。只依 x 排序一次、走過點兩遍，比起繞著樞紐依角度排序更簡單、數值上更穩健。

單趟掃描如何建出下凸包：由左到右處理各點，維護一個堆疊。對每個新點 C，只要堆疊頂端兩點 A、B 與 C 一起不構成逆時針（方向測試 A、B、C 為順時針或共線），就彈出 B；然後推入 C。這正是葛立恆掃描的彈出規則，只是套用在依 x 排序的點上，於是它把下緣描成一串左轉。接著由右到左做同樣的掃描以建出上凸包。把下鏈與上鏈接起來（去掉兩個共用端點以免角點重複），就得到逆時針順序的完整凸包。以單位正方形加中心點追蹤：下掃保留 (0,0)、(4,0)、(4,4) 並彈出中心點；上掃保留 (4,4)、(0,4)、(0,0)；接起來，凸包就是四個角點。

其成本為 O(n log n)，由單次座標排序主導；每趟掃描是 O(n)，理由與葛立恆掃描相同——推入一次、最多彈出一次的攤還論證。和葛立恆掃描相比，它完全避免計算或比較角度，因而繞開了一整類精度與平手處理的麻煩，是大多數競賽程式設計者所背的版本。同樣誠實的提醒仍適用：對凸包邊上的共線點該如何處理（全部保留，或只留兩端極點），是你必須刻意決定的，並編碼在「彈出條件是否拒絕共線三元組」之中。