Integrálně konvexní sada - Integrally-convex set

An integrálně konvexní sada je diskrétní geometrie analogie pojmu konvexní sada v geometrii.

Podmnožina X celočíselné mřížky ${ displaystyle mathbb {Z} ^ {n}}$ je integrálně konvexní, pokud existuje y v konvexní obal z X lze vyjádřit jako a konvexní kombinace bodů X které jsou „blízko“ y, kde „blízko“ znamená, že vzdálenost mezi oběma souřadnicemi je menší než 1. ^[1]

Definice

Nechat X být podmnožinou ${ displaystyle mathbb {Z} ^ {n}}$.

Označit ch (X) konvexní obal z X. Všimněte si, že ch (X) je podmnožinou ${ displaystyle mathbb {R} ^ {n}}$, protože obsahuje všechny skutečné body, které jsou konvexními kombinacemi celočíselných bodů X.

Pro jakýkoli bod y v ${ displaystyle mathbb {R} ^ {n}}$, označují poblíž (y) := {z v ${ displaystyle mathbb {Z} ^ {n}}$ | |z_i - y_i| <1 pro všechny i v 1,...,n}}. Jedná se o celočíselné body, které jsou považovány za „blízké“ skutečnému bodu y.

Podmnožina X z ${ displaystyle mathbb {Z} ^ {n}}$ je nazýván integrálně konvexní pokud každý bod y v ch (X) je také v ch (X ∩ poblíž (y)).^[2]

Příklad

Neintegrálně konvexní sada

Nechat n = 2 a nechat X = {(0,0), (1,0), (2,0), (2,1)}. Jeho konvexní trup ch (X) obsahuje například bod y = (1.2, 0.5).

Celé číslo poblíž y jsou blízko (y) = {(1,0), (2,0), (1,1), (2,1)}. Tak X ∩ poblíž (y) = {(1,0), (2,0), (2,1)}. Ale y není v ch (X ∩ poblíž (y)). Viz obrázek vpravo.

Proto X není integrálně konvexní.^[1]

Naproti tomu sada Y = {(0,0), (1,0), (2,0), (1,1), (2,1)} je integrálně konvexní.

Vlastnosti

Iimura, Murota a Tamura^[3] ukázaly následující vlastnost integrálně konvexní množiny.

Nechat ${ displaystyle X podmnožina mathbb {Z} ^ {n}}$ být konečná integrálně konvexní množina. Existuje a triangulace ch (X) to je integrální, tj.:

• Vrcholy triangulace jsou vrcholy X;
• Vrcholy každého simplexu triangulace leží ve stejné „buňce“ (hyperkrychle délky strany 1) celočíselné mřížky ${ displaystyle mathbb {Z} ^ {n}}$.

Integrálně konvexní sada

Sada příkladů X není integrálně konvexní a skutečně ch (X) nepřipouští integrální triangulaci: každá triangulace ch (X), buď musí přidat vrcholy, které nejsou v X, nebo musí zahrnovat jednoduchosti, které nejsou obsaženy v jedné buňce.

Naproti tomu sada Y = {(0,0), (1,0), (2,0), (1,1), (2,1)} je integrálně konvexní a skutečně připouští integrální triangulaci, např. se třemi jednoduchostmi {(0,0), (1,0), (1,1)} a {(1,0), (2,0), (2,1)} a {(1,0) , (1,1), (2,1)}. Viz obrázek vpravo.

Reference