凸包

在一个实数向量空間中，对于给定集合，所有包含X的凸集的交集被称为的凸包。

的凸包可以用内所有点的线性组合来构造。

在二维欧几里得空间中，凸包可想象為一條剛好包著所有點的橡皮圈。

演算法
增量式算法
逐次將點加入，然後檢查之前的點是否在新的凸包上。由於每次都要檢查所有之前的點，時間複雜度為。

 包裹法（Jarvis步进法）

首先由一點必定在凸包的點開始，例如最左的一點。然後選擇點使得所有點都在的右方，這步驟的時間複雜度是，要比較所有點以為原點的極坐標角度。以為原點，重覆這個步驟，依次找到。這總共有步。因此，時間複雜度為。

葛立恒（Graham）扫描法 
right

由最底的一點開始（如果有多个这样的点，那么选择最左边的），計算它跟其他各點的連線和x軸正向的角度，按小至大將這些点排序，稱它們的對應點為。這裡的時間複雜度可達。

考慮最小的角度對應的點。若由到的路徑相對到的路徑是向右轉的（可以想象一個人沿走到，他站在時，是向哪邊改變方向），表示不可能是凸包上的一點，考慮下一點由到的路徑；否則就考慮到的路徑是否向右轉……直到回到。

這個演算法的整體時間複雜度是，注意每點只會被考慮一次，而不像Jarvis步进法中會考慮多次。

這個演算法由葛立恆在1972年發明。Graham, R.L. (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133它的缺點是不能推廣到二維以上的情況。

單調鏈
將點按x坐標的值排列，再按y坐標的值排列。

選擇x坐標為最小值的點，在這些點中找出y坐標的值最大和y坐標的值最小的點。對於x坐標為最大值也是這樣處理。將兩組點中y坐標值較小的點連起。在這條線段下的點，找出它們之中y坐標值最大的點，又在它們之間找x坐標值再最小和最大的點……如此類推。

時間複雜度是。

分治法
將點集X分成兩個不相交子集。求得兩者的凸包後，計算這兩個凸包的凸包，該凸包就是X的凸包。時間複雜度是。

快包法（Akl-Toussaint启发式）
選擇最左、最右、最上、最下的點，它們必組成一個凸四邊形（或三角形）。這個四邊形內的點必定不在凸包上。然後將其餘的點按最接近的邊分成四部分，再進行快包法（QuickHull）。

各种星形多面体的凸包
 多面体名称  凸包 小星形十二面体  正二十面体 大十二面体  正二十面体 大星形十二面体  正十二面体 大二十面体  正十二面体

應用
 圖象處理
 模式識別
 地理信息系統

參考

 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Pages 955–956 of section 33.3: Finding the convex hull.
 The Convex Hull of a 2D Point Set or Polygon, by Dan Sunday
參見
 Carathéodory定理
 Delaunay三角化
外部連結
 一個展示這些演算法如何運作的Java Applet
 Convex Hull, Kin Yin Li
 QuickHull 介紹：
 Incremental(增量法) 介紹
 Jarvis March (Gift Wripping)介紹：

Category:多胞形
Category:算法
Category:凸几何
Category:計算幾何
分类:数学概念