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 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 .
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]
Example[]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/80/Non-integrally-convex.svg/220px-Non-integrally-convex.svg.png)
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.
Properties[]
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 .
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Integrally-convex-with-triangulation.svg/220px-Integrally-convex-with-triangulation.svg.png)
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[]
- ^ a b Yang, Zaifu (2009-12-01). "Discrete fixed point analysis and its applications". Journal of Fixed Point Theory and Applications. 6 (2): 351–371. doi:10.1007/s11784-009-0130-9. ISSN 1661-7746. S2CID 122640338.
- ^ Chen, Xi; Deng, Xiaotie (2006). Chen, Danny Z.; Lee, D. T. (eds.). "A Simplicial Approach for Discrete Fixed Point Theorems". Computing and Combinatorics. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 4112: 3–12. doi:10.1007/11809678_3. ISBN 978-3-540-36926-4.
- ^ Iimura, Takuya; Murota, Kazuo; Tamura, Akihisa (2005-12-01). "Discrete fixed point theorem reconsidered". Journal of Mathematical Economics. 41 (8): 1030–1036. doi:10.1016/j.jmateco.2005.03.001. ISSN 0304-4068.
- Discrete geometry