Riktningsbevarande funktion

Inom diskret matematik är en riktningsbevarande funktion (eller kartläggning) en funktion på ett diskret utrymme, såsom heltalsrutnätet, som (informellt) inte förändras för drastiskt mellan två intilliggande punkter. Det kan betraktas som en diskret analog till en kontinuerlig funktion .

Konceptet definierades först av Iimura. Vissa varianter av det definierades senare av Yang, Chen och Deng, Herings, van-der-Laan, Talman och Yang och andra.

Grundläggande koncept

Vi fokuserar på funktionerna ${\displaystyle f:X\to \mathbb {R} ^{n}} ,$ där domänen X är en finit delmängd av det euklidiska rummet $\mathbb {R } ^{n}$ . ch( X ) betecknar det konvexa skrovet på X .

Det finns många varianter av riktningsbevarande egenskaper, beroende på hur exakt man definierar den "drastiska förändringen" och de "intilliggande punkterna". När det gäller den "drastiska förändringen" finns det två huvudvarianter:

Riktningsbevarande (DP) betyder att, om x och y ligger intill varandra, så för alla $i\in [n]$ : $f_ {i}(x)\cdot f_{i}(y)\geq 0$ . Med ord: varje komponent i funktionen f får inte byta tecken mellan angränsande punkter.
Bruttoriktningsbevarande (BNP) betyder att, om x och y ligger intill varandra, då $f(x)\cdot f(y)\geq 0$ . Med ord: riktningen för funktionen f (som vektor) ändras inte med mer än 90 grader mellan angränsande punkter. Observera att DP innebär BNP men inte vice versa.

När det gäller de "intilliggande punkterna" finns det flera varianter:

Hyperkubisk betyder att x och y är intilliggande om de finns i någon axlar-parallell hyperkub med sidolängd 1.
Simplicial betyder att x och y är intilliggande om de är hörn av samma simplex, i någon triangulering av domänen. Vanligtvis är enkel adjacency mycket starkare än hyperkubisk adjacency; följaktligen är hyperkubisk DP mycket starkare än enkel DP.

Specifika definitioner presenteras nedan. Alla exempel nedan är för $n=2$ dimensioner och för X = { (2,6), (2,7), (3, 6), (3, 7) }.

Egenskaper och exempel

Hyperkubisk riktningsbevarande

En cell är en delmängd av $\mathbb {R} ^{n}$ som kan uttryckas med $+[0,1]^{n}}$ för vissa $k\in \mathbb {Z} ^{n}$ . Till exempel är kvadraten $[2,3]\times [6,7]$ en cell.

Två punkter i $\mathbb {R} ^{n}$ kallas cellanslutna om det finns en cell som innehåller båda.

Hyperkubiska riktningsbevarande egenskaper kräver att funktionen inte förändras för drastiskt i cellanslutna punkter (punkter i samma hyperkubiska cell).

f ^a	6	7
2	(2,1)	(1,1)
3	(0,1)	(0,0)

f kallas hyperkubisk riktningsbevarande (HDP) om, för något par av cellanslutna punkter x , y i X, för alla $i\in [n]$ : $f_{i}(x)\cdot f_{i}(y)\geq 0$ . Begreppet lokalt riktningsbevarande (LDP) används ofta istället. Funktionen f ^a till höger är DP.

Vissa författare använder en variant som kräver att för alla par av cellanslutna punkter x , y i X, för alla $i\in [n]$ : $(f_{i}(x)-x_{i})\cdot (f_{i}(y)-y_{i})\geq 0$ . En funktion f ( x ) är HDP av den andra varianten, om funktionen g ( x ):= f ( x )- x är HDP av den första varianten.

f ^b	6	7
2	(2,1)	(1,1)
3	(1,-1)	(0,0)

f kallas hyperkubisk bruttoriktningsbevarande (HGDP) , eller lokalt bruttoriktningsbevarande (LGDP) , om för något par av cellanslutna punkter x , y i X, $f( x)\cdot f(y)\geq 0$ . Varje HDP-funktion är HGDP, men det omvända är inte sant. Funktionen f ^b är HGDP, eftersom skalärprodukten av varannan vektor i tabellen är icke-negativ. Men det är inte HDP, eftersom den andra komponenten växlar tecken mellan (2,6) och (3,6): $f_ {2}^{b}(2,6)\cdot f_{2}^{b}(3,6)=-1<0$ .

Vissa författare använder en variant som kräver att för alla par av cellanslutna punkter x , y i X, $(f(x)-x )\cdot (f(y)-y)\geq 0$ . En funktion f ( x ) är HGDP av den andra varianten, om funktionen g ( x ):= f ( x )- x är HGDP av den första varianten.

Enkelt riktningsbevarande

En simplex kallas integral om alla dess hörn har heltalskoordinater, och de alla ligger i samma cell (så skillnaden mellan koordinater för olika hörn är högst 1).

En triangulering av någon delmängd av $\mathbb {R} ^{n}$ kallas integral om alla dess förenklingar är integraler.

Givet en triangulering kallas två punkter förenklat sammankopplade om det finns en simplex av trianguleringen som innehåller dem båda.

Observera att i en integral triangulering är alla enkelt anslutna punkter också cellanslutna, men det omvända är inte sant. Tänk till exempel på cellen $[2,3]\times [6,7]$ . Betrakta integraltrianguleringen som delar upp den i två trianglar: {(2,6),(2,7),(3,7)} och {(2,6),(3,6),(3,7)} . Punkterna (2,7) och (3,6) är cellanslutna men inte förenklade.

Enkla riktningsbevarande egenskaper förutsätter viss fast integral triangulering av ingångsdomänen. De kräver att funktionen inte förändras för drastiskt i enkelt sammankopplade punkter (punkter i samma simplex i trianguleringen). Detta är generellt sett ett mycket svagare krav än hyperkubisk riktningskonservering.

f kallas för enkel riktningsbevarande (SDP) om, för någon integral triangulering av X , för något par av enkelt sammankopplade punkter x , y i X, för alla $i\in [n]$ : $(f_{i}(x)-x_{i})\cdot (f_{i}(y)- y_{i})\geq 0$ .

f ^c	6	7
2	(2,1)	(1,1)
3	(1,-2)	(0,0)

f kallas för enkelt bruttoriktningsbevarande (SGDP) eller förenklat lokalt bruttoriktningsbevarande (SLGDP) om det finns en integrerad triangulering av ch( X ) så att, för alla par enkelt sammankopplade punkter x , y i X, $f(x)\cdot f(y)\geq 0$ .

Varje HGDP-funktion är SGDP, men HGDP är mycket starkare: den är ekvivalent med SGDP med hänsyn till alla möjliga integraltrianguleringar av ch( X ), medan SGDP relaterar till en enda triangulering. Som ett exempel är funktionen f ^c till höger SGDP genom trianguleringen som delar upp cellen i de två trianglarna {(2,6),(2,7),(3,7)} och {(2,6) ,(3,6),(3,7)}, eftersom skalärprodukten av varannan vektor i varje triangel är icke-negativ. Men det är inte HGDP, eftersom $f^{c}(3,6)\cdot f^{c}(2,7 )=-1<0$ .