凸包

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

凸包（Convex hull）：彈性繩帶的類比。

$S:=\bigcap _{X\subseteq K\subseteq V \atop K\ {\mathrm {is\ convex} }}K.$

$X$的凸包可以用$X$内所有点$(x_{1},\ldots ,x_{n})$的线性组合来构造。

$S:=\left\{\left.\,\sum _{j=1}^{n}t_{j}x_{j}\,\right|x_{j}\in X,\,\sum _{j=1}^{n}t_{j}=1,\,t_{j}\in \lbrack 0,1\rbrack \,\right\}.$

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

演算法

增量式算法

逐次將點加入，然後檢查之前的點是否在新的凸包上。由於每次都要檢查所有之前的點，時間複雜度為$O(n^{2})$ 。

包裹法（Jarvis步进法）

首先由一點必定在凸包的點開始，例如最左的一點$A_{1}$ 。然後選擇$A_{2}$ 點使得所有點都在$A_{1}A_{2}$ 的右方，這步驟的時間複雜度是$O(n)$ ，要比較所有點以$A_{1}$ 為原點的極坐標角度。以$A_{2}$ 為原點，重覆這個步驟，依次找到$A_{3},A_{4},...,A_{k},A_{1}$ 。這總共有$k$ 步。因此，時間複雜度為$O(kn)$ 。

葛立恒（Graham）扫描法

 

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

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

這個演算法的整體時間複雜度是$O(n\log {n})$ ，注意每點只會被考慮一次，而不像Jarvis步进法中會考慮多次。

這個演算法由葛立恆在1972年發明。^[1]它的缺點是不能推廣到二維以上的情況。

單調鏈

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

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

時間複雜度是$O(n\log {n})$ 。

分治法

將點集X分成兩個不相交子集。求得兩者的凸包後，計算這兩個凸包的凸包，該凸包就是X的凸包。時間複雜度是$O(n\log {n})$ 。

快包法（Akl-Toussaint启发式）

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

各种星形多面体的凸包

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

應用

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

參考

1. Graham, R.L. (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133

• 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三角化

外部連結

• QuickHull 介紹：（页面存档备份，存于互联网档案馆）
• Incremental(增量法) 介紹（页面存档备份，存于互联网档案馆）
• Jarvis March (Gift Wripping)介紹：（页面存档备份，存于互联网档案馆）