凸包
有限な点集合の凸包は、それに属する点から得られる凸結合全体の成す集合である。凸結合における S の各点 xi に掛かる重みあるいは係数 αi は、全て正かつそれらの総和が 1 となるものであり、これらの重みは点の間の重み付き平均の計算に用いられる。このような係数の組を選ぶごとに凸包に属する点が一つ定まり、係数として可能な全ての組を考えることによって凸包の全体が得られる。式にすれば、凸包は
{ ∑ i = 1 | S | α i x i | ( ∀ i : α i ≥ 0 ) ∧ ∑ i = 1 | S | α i = 1 } {\displaystyle \left\{\sum _{i=1}^{|S|}\alpha _{i}x_{i}{\mathrel {\;{\Bigg |}\;}}(\forall i:\alpha _{i}\geq 0)\wedge \sum _{i=1}^{|S|}\alpha _{i}=1\right\}}
で与えられる集合ということになる。R 内の有限点集合 S の凸包は、平面の場合は凸多角形、三次元空間の場合は凸多面体、より一般の次元では凸超多面体(英語版)または凸多胞体)と呼ばれる。
計算幾何学において、点やその他の幾何学的対象のなす有限集合の凸包を計算するアルゴリズムが数多く知られている。ギフト包装法などがある。
「凸包の計算」というのは、曖昧さ無く効果的に求める凸図形を表すデータを構築することを意味する。凸包アルゴリズムの計算量は通例、入力点の数 n と凸包に属する点(出力点)の数 h とに関して評価される。
二次元及び三次元の点集合に対して、計算量 O(n log h) で凸包を計算できる出力依存アルゴリズムが知られている。三次元より高次の d-次元では、凸包の計算時間は最悪の場合で O ( n ⌊ d / 2 ⌋ ) {\displaystyle O(n^{\lfloor d/2\rfloor })} となる。