凸包

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

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）。

各种星形多面体的凸包

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

应用

参考

^ 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（页面存档备份，存于互联网档案馆）

参见

外部链接

一个展示这些算法如何运作的Java Applet
Convex Hull, Kin Yin Li
QuickHull 介绍：（页面存档备份，存于互联网档案馆）
Incremental(增量法) 介绍（页面存档备份，存于互联网档案馆）
Jarvis March (Gift Wripping)介绍：（页面存档备份，存于互联网档案馆）

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

[1]