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 $\mathbb {Z} ^{n}$ 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 $\mathbb {Z} ^{n}$.

Denote by ch(X) the convex hull of X. Note that ch(X) is a subset of $\mathbb {R} ^{n}$, since it contains all the real points that are convex combinations of the integer points in X.

For any point y in $\mathbb {R} ^{n}$, denote near(y)  := {z in $\mathbb {Z} ^{n}$ | |z_i - y_i| < 1 for all i in {1,...,n} }. These are the integer points that are considered "nearby" to the real point y.

A subset X of $\mathbb {Z} ^{n}$ is called integrally convex if every point y in ch(X) is also in ch(X ∩ near(y)).

Example

Let n = 2 and let X = { (0,0), (1,0), (2,0), (2,1) }. Its convex hull ch(X) contains, for example, the point y = (1.2, 0.5).

The integer points nearby y are near(y) = {(1,0), (2,0), (1,1), (2,1) }. So X ∩ near(y) = {(1,0), (2,0), (2,1)}. But y is not in ch(X ∩ near(y)).

Therefore X is not integrally-convex.

In contrast, the set { (0,0), (1,0), (2,0), (1,1), (2,1) } is integrally-convex.