Integrally convex set


An integrally convex set is the discrete geometry analogue of the concept of convex set in geometry.
A subset X of the integer grid is integrally convex if any point y in the convex hull of X can be expressed as a convex combination of the points of X that are "near" y, where "near" means that the distance between each two coordinates is less than 1.

Definitions

Let X be a subset of.
Denote by ch the convex hull of X. Note that ch is a subset of, since it contains all the real points that are convex combinations of the integer points in X.
For any point y in, denote near := . These are the integer points that are considered "nearby" to the real point y.
A subset X of is called integrally convex if every point y in ch is also in ch.

Example

Let n = 2 and let X =. Its convex hull ch contains, for example, the point y =.
The integer points nearby y are near =. So X ∩ near =. But y is not in ch. See image at the right.
Therefore X is not integrally convex.
In contrast, the set Y = is integrally convex.

Properties

Iimura, Murota and Tamura have shown the following property of integrally convex set.
Let be a finite integrally convex set. There exists a triangulation of ch that is integral, i.e.:
  • The vertices of the triangulation are the vertices of X;
  • The vertices of every simplex of the triangulation lie in the same "cell" of the integer grid.
The example set X is not integrally convex, and indeed ch does not admit an integral triangulation: every triangulation of ch, either has to add vertices not in X, or has to include simplices that are not contained in a single cell.
In contrast, the set Y = is integrally convex, and indeed admits an integral triangulation, e.g. with the three simplices and and. See image at the right.