Integrally convex set explained

An integrally convex set is the discrete geometry analogue of the concept of convex set in geometry.

A subset X of the integer grid

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.^[1]

Definitions

Let X be a subset of

Z ^{n} .

Denote by ch(X) the convex hull of X. Note that ch(X) is a subset of

R ^{n} , since it contains all the real points that are convex combinations of the integer points in X.

For any point y in

R ^{n} , denote near(y) := . These are the integer points that are considered "nearby" to the real point y.

A subset X of

Z ^{n} is called integrally convex if every point y in ch(X) is also in ch(X ∩ near(y)).^[2]

Example

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

The integer points nearby y are near(y) = . So X ∩ near(y) = . But y is not in ch(X ∩ near(y)). See image at the right.

Therefore X is not integrally convex.

In contrast, the set Y = is integrally convex.

Properties

Iimura, Murota and Tamura^[3] have shown the following property of integrally convex set.

Let

X\subset Z ^{n} be a finite integrally convex set. There exists a triangulation of ch(X) 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" (hypercube of side-length 1) of the integer grid

Z ^{n} .

The example set X is not integrally convex, and indeed ch(X) does not admit an integral triangulation: every triangulation of ch(X), 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.

Notes and References

1. Yang. Zaifu. 2009-12-01. Discrete fixed point analysis and its applications. Journal of Fixed Point Theory and Applications. en. 6. 2. 351–371. 10.1007/s11784-009-0130-9. 122640338. 1661-7746.
2. Book: Chen. Xi. Deng. Xiaotie. Computing and Combinatorics . A Simplicial Approach for Discrete Fixed Point Theorems . 2006. Chen. Danny Z.. Lee. D. T.. Lecture Notes in Computer Science. 4112. en. Berlin, Heidelberg. Springer. 3–12. 10.1007/11809678_3. 978-3-540-36926-4.
3. Iimura. Takuya. Murota. Kazuo. Tamura. Akihisa. 2005-12-01. Discrete fixed point theorem reconsidered. Journal of Mathematical Economics. en. 41. 8. 1030–1036. 10.1016/j.jmateco.2005.03.001. 0304-4068.