葛立恆掃描（Graham scan）
/ GRAY-am scan /
葛立恆掃描（Graham scan）是建立凸包的經典 O(n log n) 做法。其想法是先選定一個確定的起始角點，把其餘的點依角度繞著它展開，再一次走過它們，同時維護一個凸包候選堆疊，並把任何會造成凹陷的點彈出。這就像從房間一角繞著掃動手電筒光束、描出輪廓：光束旋轉時，每個被新照亮的點，要嘛延續平滑的外緣，要嘛揭示前一個點其實是該抹掉的凹口。
具體做法：(1) 找出最低點 P0（y 最小，平手時取 x 最小）——它保證在凸包上。(2) 把其餘各點依其與 P0 形成的極角排序，於是你會以逆時針順序拜訪它們。(3) 把 P0 與第一個點推入堆疊，接著對每個剩下的點 C，看堆疊頂端兩點 A（下面）與 B（頂端）：只要三元組 A、B、C 不構成逆時針（左轉）——也就是對 A、B、C 做方向測試得到順時針或共線——就把 B 彈出，因為 B 是凹陷。然後推入 C。結束時，堆疊裡就是逆時針順序的凸包頂點。彈出動作正是把內部凸起削掉的關鍵。小追蹤：以單位正方形加中心點為例，中心點被推入後，下一個角點一揭示它造成右轉，就立刻被彈出。
為何是 O(n log n)：排序以 O(n log n) 主導，掃描本身是 O(n)，因為每個點被推入一次、最多被彈出一次，故總推入／彈出工作是線性的（一個攤還論證）。葛立恆掃描以整數方向測試實作時是精確的，但有兩個誠實的陷阱：凸包邊上的共線點需要在角度排序中訂出平手規則（決定保留或丟棄），而極角排序正是微妙錯誤的藏身處。基於這些原因，許多人偏好安德魯單調鏈，它改以座標而非角度排序，較容易寫對。
點集 {(0,0),(4,0),(4,4),(0,4),(2,2)}：P0 = (0,0)。其餘依角度排序：(4,0)、(2,2)、(4,4)、(0,4)。推入 (0,0)、(4,0)。加入 (2,2)：左轉，保留。加入 (4,4)：A=(4,0)、B=(2,2)、C=(4,4) 為右轉 -> 彈出 (2,2)，再推入 (4,4)。加入 (0,4)：左轉，保留，推入 (0,4)。堆疊 = 四個角點。
從最低點依角度排序，再彈出任何造成非左轉的頂點。
掃描為 O(n) 只是攤還意義上的主張：整趟執行中每個點最多被彈出一次，儘管單一步驟可能連續彈出許多點。