Top Qs
Timeline
Chat
Perspective
Integrally convex set
From Wikipedia, the free encyclopedia
Remove ads
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.[1]
Remove ads
Definitions
Let X be a subset of .
Denote by ch(X) the convex hull of X. Note that ch(X) 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(y) := {z in | |zi - yi| < 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 is called integrally convex if every point y in ch(X) is also in ch(X ∩ near(y)).[2]
Remove ads
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)). See image at the right.
Therefore X is not integrally convex.[1]
In contrast, the set Y = { (0,0), (1,0), (2,0), (1,1), (2,1) } is integrally convex.
Remove ads
Properties
Summarize
Perspective
Iimura, Murota and Tamura[3] have shown the following property of integrally convex set.
Let 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 .

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 = { (0,0), (1,0), (2,0), (1,1), (2,1) } is integrally convex, and indeed admits an integral triangulation, e.g. with the three simplices {(0,0),(1,0),(1,1)} and {(1,0),(2,0),(2,1)} and {(1,0),(1,1),(2,1)}. See image at the right.
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads