Integrerat konvex set

En integrerat konvex uppsättning är den diskreta geometrianalogen till begreppet konvex uppsättning i geometri.

En delmängd X av heltalsrutnätet $\mathbb {Z} ^{n}$ är integralt konvex om någon punkt y i det konvexa skrovet av X kan uttryckas som en konvex kombination av punkterna på X som är " nära" y , där "nära" betyder att avståndet mellan varje två koordinater är mindre än 1.

Definitioner

Låt X vara en delmängd av $\mathbb {Z} ^{n}$ .

Beteckna med ch( X ) det konvexa skrovet på X . Observera att ch( X ) är en delmängd av $\mathbb {R} ^{n}$ , eftersom den innehåller alla reella punkter som är konvexa kombinationer av heltalspunkterna i X .

För valfri punkt y i $\mathbb {R} ^{n}$ , beteckna near( y ) := { z i $\mathbb {Z} ^{n}$ | | z _i - y _i | < 1 för alla i i {1,..., n } }. Dessa är heltalspunkterna som anses vara "nära" den verkliga punkten y .

En delmängd X av $\mathbb {Z} ^{n}$ kallas integralt konvex om varje punkt y i ch( X ) också är i ch( X ∩ nära( y )).

Exempel

Ej integrerat konvex set

Låt n = 2 och låt X = { (0,0), (1,0), (2,0), (2,1) }. Dess konvexa skrov ch( X ) innehåller till exempel punkten y = (1,2, 0,5).

Heltalspunkterna i närheten av y är nära( y ) = {(1,0), (2,0), (1,1), (2,1) }. Så X ∩ nära( y ) = {(1,0), (2,0), (2,1)}. Men y är inte i ch( X ∩ nära( y )). Se bilden till höger.

Därför är X inte integrerat konvext.

Däremot är mängden Y = { (0,0), (1,0), (2,0), (1,1), (2,1) } integralt konvex.

Egenskaper

Iimura, Murota och Tamura har visat följande egenskap av integrerat konvex uppsättning.

Låt $X\subset \mathbb {Z} ^{n}$ vara en ändlig integralt-konvex mängd. Det finns en triangulering av ch( X ) som är integral , dvs:

• Trianguleringens hörn är hörnen på X ;
• Hörnen för varje simplex i trianguleringen ligger i samma "cell" (hyperkub med sidolängd 1) i heltalsrutnätet $\mathbb {Z} ^{n}$ .

Integrerat konvex set

Exempelmängden X är inte integralt konvex, och ch( X ) tillåter faktiskt inte en integraltriangulering: varje triangulering av ch( X ), måste antingen lägga till hörn som inte är i X , eller måste inkludera förenklingar som inte ingår i en enda cell.

Däremot är mängden Y = { (0,0), (1,0), (2,0), (1,1), (2,1) } integralt-konvex, och medger verkligen en integral triangulering, t.ex. med de tre förenklingarna {(0,0),(1,0),(1,1)} och {(1,0),(2,0),(2,1)} och {(1,0) ),(1,1),(2,1)}. Se bilden till höger.