整数凸集合

整凸集合は、幾何学における凸集合の概念の離散幾何学における類似物です。

整数グリッドの部分集合X が整数凸包であるとは、 Xの凸包内の任意の点y が、 yに「近い」Xの点の凸結合として表現できる場合である。ここで「近い」とは、2つの座標間の距離が1未満であることを意味する。^[1]${\displaystyle \mathbb {Z} ^{n}}$

Xを のサブセットとします。 ${\displaystyle \mathbb {Z} ^{n}}$

Xの凸包をch( X )で表します。 ch( X ) はX内の整数点の凸結合である実数点をすべて含むため、のサブセットであることに注意してください。 ${\displaystyle \mathbb {R} ^{n}}$

内の任意の点yについて、 near( y ) := { z in | | z _i - y _i | < 1 for all i in {1,..., n } } と表記します。これらは、実数点yの「近くにある」と見なされる整数点です。 ${\displaystyle \mathbb {R} ^{n}}$${\displaystyle \mathbb {Z} ^{n}}$

部分集合Xが整数凸であるとは、 ch( X )内のすべての点yがch( X∩near ( y ))にも含まれる場合をいう。^[2]${\displaystyle \mathbb {Z} ^{n}}$

n = 2、X = { (0,0), (1,0), (2,0), (2,1) }とします。その凸包ch( X )には、例えば点y = (1.2, 0.5)が含まれます。

yの近くの整数点はnear( y ) = {(1,0), (2,0), (1,1), (2,1) }です。したがって、 X ∩ near( y ) = {(1,0), (2,0), (2,1)} です。ただし、y はch( X ∩ near( y ))には含まれません。右の画像を参照してください。

したがってXは整数的に凸ではない。^[1]

対照的に、集合Y = { (0,0), (1,0), (2,0), (1,1), (2,1) } は積分凸です。

飯村、室田、田村^[3]は、整凸集合の以下の性質を示した。

を有限の整凸集合とする。ch ( X) の整三角形分割が存在する。すなわち、 ${\displaystyle X\subset \mathbb {Z} ^{n}}$

• 三角形分割の頂点はXの頂点です。
• 三角形分割の各単体の頂点は、整数グリッドの同じ「セル」（辺の長さが 1 の超立方体）内にあります。${\displaystyle \mathbb {Z} ^{n}}$

例の集合X は整数凸ではなく、実際 ch( X ) は整数三角形分割を許容しません。つまり、 ch( X ) のすべての三角形分割は、 Xにない頂点を追加するか、単一のセルに含まれていない単体を含める必要があります。

対照的に、集合Y = { (0,0), (1,0), (2,0), (1,1), (2,1) } は積分凸であり、実際に、例えば 3 つの単体 {(0,0),(1,0),(1,1)} と {(1,0),(2,0),(2,1)} と {(1,0),(1,1),(2,1)} による積分三角分割が可能です。右の図を参照してください。