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^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^n$.

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

For any point ''y'' in $\mathbb^n$, denote near(''y'') := . These are the integer points that are considered "nearby" to the real point ''y''.

A subset ''X'' of $\mathbb^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'' = . 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 have shown the following property of integrally convex set.

Let $X\subset \mathbb^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 $\mathbb^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.

References

{{reflist

Discrete geometry