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

Thumb
Non-integrally convex set

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 .
Thumb
Integrally convex set

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

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads