シャープレー＝フォークマン補題

集合は、それに属する任意の2点を結ぶ線分がその集合の部分集合である場合、凸集合であるという。充実した単位円板${\displaystyle \bullet }$は凸集合であるが、単位円${\displaystyle \circ }$はそうではない。なぜなら、2つの異なる点${\displaystyle \oslash }$を結ぶ線分が円の部分集合ではないからである^[7]。集合${\displaystyle Q}$の凸包は、${\displaystyle Q}$を含む最小の凸集合である^[8]。

ミンコフスキー加法とは、複数の集合の元からそれぞれ1つずつ選び、その和を取った集合を作る操作である^[9]。例えば、0と1からなる集合をそれ自身に加えると、0、1、2からなる集合が得られる： $${\displaystyle {0,1}+{0,1}={0+0,0+1,1+0,1+1}={0,1,2}}$$ この整数部分集合${\displaystyle {0,1,2}}$は実数の区間${\displaystyle [0,2]}$に含まれ、これがその凸包である。シャープレー＝フォークマン補題は、${\displaystyle [0,2]}$の任意の点が${\displaystyle {0,1}}$の元と${\displaystyle [0,1]}$の元の和として表せることを示唆する。すなわち、${\displaystyle {0,1}}$のミンコフスキー和の凸包を得るには、加数のうち1つだけをその凸包に置き換えればよい^[10]。

非凸集合${\displaystyle {0,1}}$とその凸包${\displaystyle [0,1]}$とのハウスドルフ距離は${\displaystyle {\tfrac {1}{2}}}$であり、この距離は非凸集合${\displaystyle {0,1,2}}$とその凸包${\displaystyle [0,2]}$でも同じである。両方の場合で、凸包には${\displaystyle {\tfrac {1}{2}}}$のように非凸集合の元から距離${\displaystyle {\tfrac {1}{2}}}$の点が含まれる。この例では、ミンコフスキー加法は和とその凸包との距離を減少させない。しかし、和を算術平均に置き換え、和をその項数で割ることによりスケーリングすると、スケーリングされたミンコフスキー和とその凸包との距離は減少する。例えば、平均ミンコフスキー和 $${\displaystyle {\frac {1}{2}}\left(\{0,1\}+\{0,1\}\right)=\left\{0,{\tfrac {1}{2}},1\right\}}$$ とその凸包${\displaystyle [0,1]}$との距離は${\displaystyle {\tfrac {1}{4}}}$であり、これは加数${\displaystyle {0,1}}$とその凸包${\displaystyle [0,1]}$との距離${\displaystyle {\tfrac {1}{2}}}$の半分である。より多くの集合を加えるにつれて、その和の平均は凸包を「埋めていき」、平均とその凸包との最大距離は加数が増えるにつれてゼロに近づく。この距離の減少は、シャープレー＝フォークマン補題の帰結として、シャープレー＝フォークマン定理およびシャープレー＝フォークマン＝スター定理によってより形式的に述べられる^[10]。