Hilbert görbe

A Hilbert görbe egy folyamatos görbét töltés egy négyzet . Ez először írta le a német matematikus , David Hilbert a 1891 .

Mivel négyzetet fed le, Hausdorff-dimenziója és topológiai dimenziója megegyezik 2-vel. Ugyanakkor a fraktálok részének tekintik .

A euklideszi hossza a H N (a folytonos közelítő görbét kapunk a n -edik iteráció) van  ; ez tehát exponenciálisan nő a n . 2nem-12nem{\ displaystyle 2 ^ {n} - {1 \ felett 2 ^ {n}}}

A többdimenziós adatbázisok böngészéséhez a Hilbert-görbét javasolták a Lebesgue-görbe helyett, mert a viselkedése jobban megőrzi a lokalitást.

Geometriai felépítés

Hilbert határozza meg a funkciót , mint egy határérték funkciók amely az egymást követő közelítések a Hilbert görbe. f:[0,1]→[0,1]2{\ displaystyle f: [0.1] \ - [0.1] ^ {2}}fnem:[0,1]→[0,1]2{\ displaystyle f_ {n}: [0,1] \ - [0,1] ^ {2}}

• A 0. lépésben a H 0 grafikon egyetlen pontra korlátozódik, amely a négyzet közepén helyezkedik el . Ez a pont egyszerre a H 0 kiindulási és végpontja . A koordináták négyzetének (1/2, 1/2) középpontja a kép az egész intervallum f 0 függvényével .[0,1]×[0,1]{\ displaystyle [0.1] \ szor [0.1]}[0,1]{\ displaystyle [0,1]}
• Az 1. lépésben az intervallumot négy egyenlő részre vágjuk, és az alosztás minden egyes intervallumát megegyezzük a kezdeti négyzet negyedével. Pontosabban, az intervallum az altérrel van társítva  ; az intervallum az altérrel van társítva  ; az intervallum az altérrel van társítva  ; végül pedig az intervallum társul az altérre . Így a négy résznégyzet lefutása a következő sorrendben történik:[0,1]{\ displaystyle [0,1]}[0,1/4]{\ displaystyle [0,1 / 4]}[0,1/2]×[0,1/2]{\ displaystyle [0.1 / 2] \ szor [0.1 / 2]}[1/4,1/2]{\ displaystyle [1 / 4,1 / 2]}[0,1/2]×[1/2,1]{\ displaystyle [0,1 / 2] \ szor [1 / 2,1]}[1/2,3/4]{\ displaystyle [1 / 2,3 / 4]}[1/2,1]×[1/2,1]{\ displaystyle [1 / 2,1] \ szor [1 / 2,1]}[3/4,1]{\ displaystyle [3 / 4,1]}[1/2,1]×[0,1/2]{\ displaystyle [1 / 2,1] \ -szer [0,1 / 2]}

1	2
0	3

Ha ezeknek a négyzeteknek a középpontjait összekötjük szegmensekkel, akkor megkapjuk a H 1 gráfot . Kezdeti pontja a koordinátapont , végpontja pedig a koordinátapont . Az f 1 függvény által paraméterezett ív elküldi a [0, 1/4] intervallumot a H 1 0 négyzetben lévő részéről, a H 1 intervallumot az 1 négyzetben, az intervallumot a részről a H 1 foglalt tér 2, és az intervallum a részét a H 1 foglalt square 3, követi a haladási irányban.(1/4,1/4){\ displaystyle (1 / 4,1 / 4)}(3/4,1/4){\ displaystyle (3 / 4,1 / 4)}[1/4,1/2]{\ displaystyle [1 / 4,1 / 2]}[1/2,3/4]{\ displaystyle [1 / 2,3 / 4]}[3/4,1]{\ displaystyle [3 / 4,1]}

• Az n lépésben az n -1 lépésben kapott felosztás minden intervallumát önmagában négyre osztjuk, csakúgy, mint a hozzá tartozó négyzetet. Jelenleg minden egyes négyzet oldala 1/2 számozott 0-3 példát a grafikon H n -1 kiszámítani az előző sor, miután alá azt egy homothety a arány 1/2, de úgy, hogy, a i változó 0 és 2 között az i négyzetbe helyezett H n -1 gráf végpontja a lehető legközelebb áll az i +1 négyzetbe helyezett H n -1 gráf kezdőpontjához . Ehhez elegendő szimmetriát végezni a növekvő átlóval szemben a 0-val jelölt négyzetben, és egy szimmetriát a csökkenő átlóval szemben a 3-as négyzetben. Így az n = 2 lépésben a haladási irány az 1. lépés minden egyes négyzete a következő:

1	2	1	2
0	3	0	3
3	2	1	0
0	1	2	3

A kezdeti pontján a grafikon H N így kapott kezdeti pontján a grafikon H n -1 négyzetes 0 a bal alsó, és a végpont a grafikon H N a végpont a grafikon H n -1 a négyzet 3, a jobb alsó sarokban. A részei H n tartalmazott mind a 4 n kis négyzetek oldalsó 1/2 n annak érdekében, az utazási van az egymást követő képek a függvény f n az egyes, egymást követő időközönként hosszúságú 1/4 N felosztásával .[0,1]{\ displaystyle [0,1]}

A H n gráfok helyi meghatározása miatt a folytonos függvények sorrendje ( f n ) egyenletesen Cauchy , ezért egységesen konvergál egy folytonos f függvénnyel, amelynek gráfja a Hilbert-görbe. Ez a grafikon sűrű a négyzetben . Ezenkívül kompakt, mint a tömör [0,1] folytonos képe, tehát zárt sűrűsége , tehát egyenlő . f egy szurjektív térkép. Soha nem levezethető. [0,1]×[0,1]{\ displaystyle [0.1] \ szor [0.1]}[0,1]×[0,1]{\ displaystyle [0.1] \ szor [0.1]}[0,1]×[0,1]{\ displaystyle [0.1] \ szor [0.1]}

Indukcióval megmutatjuk, hogy a H n grafikonok , és ezért a határ átlépésével a Hilbert-görbe szimmetrikus az x = 1/2 egyenlet vonalához képest .

Rekurzív meghatározás

A korábban definiált Hilbert-függvény f ( t ) = ( x ( t ), y ( t )) paraméterezése kielégíti, figyelembe véve a konstrukció szimmetriáit:

mert t∈[0,1/4],x(t)=y(4t)2,y(t)=x(4t)2{\ displaystyle t \ in [0,1 / 4], x (t) = {\ frac {y (4t)} {2}}, y (t) = {\ frac {x (4t)} {2} }} mert t∈[1/4,1/2],x(t)=x(4t-1)2,y(t)=1+y(4t-1)2{\ displaystyle t \ in [1 / 4,1 / 2], x (t) = {\ frac {x (4t-1)} {2}}, y (t) = {\ frac {1 + y ( 4t-1)} {2}}} mert t∈[1/2,3/4],x(t)=1+x(4t-2)2,y(t)=1+y(4t-2)2{\ displaystyle t \ in [1 / 2,3 / 4], x (t) = {\ frac {1 + x (4t-2)} {2}}, y (t) = {\ frac {1+ y (4t-2)} {2}}} mert t∈[3/4,1],x(t)=2-y(4t-3)2,y(t)=1-x(4t-3)2{\ displaystyle t \ in [3 / 4,1], x (t) = {\ frac {2-y (4t-3)} {2}}, y (t) = {\ frac {1-x ( 4t-3)} {2}}}

Szintén f ( 0 ) = (0, 0) és F ( 1 ) = (1, 0).

Ezeket a kapcsolatokat az alábbiak szerint is lefordíthatjuk. Pózoljunk:

S 0 a szimmetria az y = x egyeneshez képest S 1 a (0, 1) vektor fordítása S 2 a vektor (1,1) transzlációja S 3 a szimmetria az y = - x egyeneshez viszonyítva, a (2,1) vektor transzlációjával.

Tehát, ha az u n a t 4 alapjegye , akkor: t=0,u1u2⋯unem⋯=∑nem=0∞unem4nem{\ displaystyle t = 0, u_ {1} u_ {2} \ cdots u_ {n} \ cdots = \ sum _ {n = 0} ^ {\ infty} {\ frac {u_ {n}} {4 ^ { nem}}}}

f(t)=12Su1(f(0,u2⋯unem⋯)){\ displaystyle f (t) = {\ frac {1} {2}} S_ {u_ {1}} (f (0, u_ {2} \ cdots u_ {n} \ cdots))}

és iterálás:

f(t)=12nemSu1Su2⋯Sunem(f(0,unem⋯)){\ displaystyle f (t) = {\ frac {1} {2 ^ {n}}} S_ {u_ {1}} S_ {u_ {2}} \ cdots S_ {u_ {n}} (f (0, u_ {n} \ cdots))}}

Különösen, ha t olyan valós, amelynek véges n számjegye van a 4. alapban ( ), akkor: t=0,u1u2⋯unem{\ displaystyle t = 0, u_ {1} u_ {2} \ cdots u_ {n}}

f(t)=12nemSu1Su2⋯Sunem(f(0))=12nemSu1Su2⋯Sunem(0,0){\ displaystyle f (t) = {\ frac {1} {2 ^ {n}}} S_ {u_ {1}} S_ {u_ {2}} \ cdots S_ {u_ {n}} (f (0) ) = {\ frac {1} {2 ^ {n}}} S_ {u_ {1}} S_ {u_ {2}} \ cdots S_ {u_ {n}} (0,0)}

Így könnyen kiszámíthatjuk bármilyen mennyiség és különösen azok értékét , amelyek megadják a kis négyzetek középpontjainak koordinátáit, amikor k 1 és 4 n között változik . f(k4nem){\ displaystyle f ({\ frac {k} {4 ^ {n}}})}f(2k-12×4nem)=f(4k-24nem+1){\ displaystyle f ({\ frac {2k-1} {2 \ -szeres 4 ^ {n}}}) = f ({\ frac {4k-2} {4 ^ {n + 1}}})}

Építés diszkrét közelítésekkel

A H n gráf csúcsainak koordinátáit közvetlenül indukcióval lehet meghatározni . A fordítást úgy hajtjuk végre, hogy a kezdeti csúcs koordinátái visszakerüljenek (0,0) -ra (és ne egy kis négyzet közepére). Ennek ellenére ezt a lefordított gráfot továbbra is H n-vel fogjuk jelölni . Mi használni, hogy a segéd változót egy jelző tájolását az elmozdulás, és hogy képes venni a értéke 0, 1, 2, 3. A tájolás által adott egy fog megfelelnek a következő négy lehetséges irányait a grafikon H 1 vagy szimmetriái:

Három mátrixot is adunk magunknak:

x=(0011100111000110),Y=(0110110010010011),NÁL NÉL=(3001211012230332)←0=nál nél←1=nál nél←2=nál nél←3=nál nél{\ displaystyle X = {\ elején {pmatrix} 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \ end {pmatrix} } \ !, \, Y = {\ kezdődik {pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \ 1 & 0 \ end {pmatrix}} \ !, \; A = {\ begin {pmatrix} 3 & 0 & 0 & 1 \\ 2 & 1 & 1 & 0 \\ 1 & 2 & 2 & 3 \\ 0 & 3 & 3 & 2 \ end {pmatrix}} \; \; {\ begin {mátrix} {\ begin {tömb} {ll} \ leftarrow & 0 = a \\\ leftarrow & 1 = a \\\ leftarrow & 2 = a \\\ leftarrow & 3 = a \ end {tömb}} \ vég {mátrix}}}

A sorindexeinek változhat 0 és 3 (és nem 1-4 a szokásos módon), és ezek a mutatók megfelelnek az értékek által hozott egy . Az oszlopindexek szintén 0 és 3 között változnak, és megfelelnek az adott t paraméter 4. bázisának számjegyei által vett értékeknek . X elemei a tályogok, Y elemei pedig egy csúcs ordinátái lesznek, amelyeket ki akar számolni; A elemei megadják a számítás során követendő különféle irányokat.

Lépésben N , a grafikon (fordítás) H n van 4 n csúcsú. Taken tallózólistájában sorrendben, lesznek társítva a 4 n elemeit t az , amelynek bázis-4 bomlás pontosan n számjegyet (esetleg ideértve a végleges 0s): [0,1[{\ displaystyle [0,1 [}

tnem=0.u1u2⋯unem=∑én=1nemuén4én{\ displaystyle t_ {n} = 0.u_ {1} u_ {2} \ cdots u_ {n} = \ sum _ {i = 1} ^ {n} {\ frac {u_ {i}} {4 ^ { én}}}}, .uén∈{0,1,2,3}{\ displaystyle u_ {i} \ in \ {0,1,2,3 \}}

Tehát legyen egy ilyen szám. A H n gráf csúcsának megfelelő koordinátái a 0-tól n -ig változó k- n történő indukcióval kiszámíthatók a számnak megfelelő H k gráf csúcsának koordinátáiból . Jelöljük a koordinátáit , és hagyja, hogy legyen a paraméter értékét, amely megadja a orientációban kell elfogadni megépíteni a négy pont a grafikon H k +1 származó (beleértve a vertex , amely megfelel . tnem{\ displaystyle t_ {n}}Mnem{\ displaystyle M_ {n}}tnem{\ displaystyle t_ {n}}Mk{\ displaystyle M_ {k}}tk=0.u1u2⋯uk{\ displaystyle t_ {k} = 0.u_ {1} u_ {2} \ cdots u_ {k}}(xk,yk){\ displaystyle (x_ {k}, y_ {k})}Mk{\ displaystyle M_ {k}}nál nélk{\ displaystyle a_ {k}}Mk{\ displaystyle M_ {k}}Mk+1{\ displaystyle M_ {k + 1}}tk+1{\ displaystyle t_ {k + 1}}

A k = 0, a grafikon H 0 csökken, hogy a pont (0,0), és az orientáció meghatározására építésére H 1 megfelel a = 0. tehát kezdetben:

x0=0,y0=0,nál nél0=0{\ displaystyle x_ {0} = 0, \, y_ {0} = 0, \, a_ {0} = 0}

A k változó 1-től n- , mi majd határozza meg az indukciós a szekvenciák:

xk=xk-1+12kxnál nélk-1,uk{\ displaystyle x_ {k} = x_ {k-1} + {\ frac {1} {2 ^ {k}}} X_ {a_ {k-1}, \, u_ {k}}}

yk=yk-1+12kYnál nélk-1,uk{\ displaystyle y_ {k} = y_ {k-1} + {\ frac {1} {2 ^ {k}}} Y_ {a_ {k-1}, \, u_ {k}}}

nál nélk=NÁL NÉLnál nélk-1,uk{\ displaystyle a_ {k} = A_ {a_ {k-1}, \, u_ {k}}}

Mi valóban ellenőrizni, hogy ha a tájolás adja az értékét , akkor a különbség a koordinátákat a négy pont a grafikon H k eredő és a koordinátákat is, hogy az a tényező 1/2 k , található az index sor az X és Y mátrixok, attól függően, hogy az utolsó számjegy az adó az oszlop index el kell fogadni. Ezenkívül az így kapott ponton az új pont, amelyet a pont megalkotása érdekében el kell fogadni, az A mátrix indexsorán elhelyezkedő szám , ismét a Mátrix utolsó számjegyének függvényében . Mk-1{\ displaystyle M_ {k-1}}nál nélk-1{\ displaystyle a_ {k-1}}Mk-1{\ displaystyle M_ {k-1}}Mk-1{\ displaystyle M_ {k-1}}nál nélk-1{\ displaystyle a_ {k-1}}uk{\ displaystyle u_ {k}}tk{\ displaystyle t_ {k}}Mk{\ displaystyle M_ {k}}Mk+1{\ displaystyle M_ {k + 1}}nál nélk{\ displaystyle a_ {k}}nál nélk-1{\ displaystyle a_ {k-1}}uk{\ displaystyle u_ {k}}tk{\ displaystyle t_ {k}}

A 0,00 ... 0 és 0,33 ... 3 közötti értékek ( n számjeggyel) áthaladásakor a 4 n csúcs elfoglalja a 4 n kis négyzet bal alsó sarkát a H n grafikon sorrendjét követve.tnem{\ displaystyle t_ {n}}Mnem{\ displaystyle M_ {n}}

A négyzetek középpontjának megszerzéséhez csak adja hozzá az egyes csúcsok koordinátáihoz . 12nem+1{\ displaystyle {\ frac {1} {2 ^ {n + 1}}}}Mnem{\ displaystyle M_ {n}}

Általánosítás magasabb dimenzióban

A Hilbert-görbe magasabb dimenziókra általánosítható. Például a 3. dimenzióban az 1. lépésben elegendő a kocka nyolc csúcsát egy csúcsból egy szomszédos csúcsba haladni. Az n -1 lépéstől az n lépésig haladva az egységkockát nyolc részkockára vágjuk, amelyekben hozzávetőleges Hil -1 görbéje van, amelynek sorrendje n -1, de úgy, hogy minden n -1 rendű gráf végpontja a lehető legközelebb álljon a következő n -1 sorrendű grafikon kezdeti csúcsához .

Az általánosítás funkcionális összetétel útján is elvégezhető. Így a 4. dimenzió Hilbert-görbéje meghatározható f ( t ) = ( x ( x ( t )), y ( x ( t )), x ( y ( t )), y ( y ( t ))). Ez a meghatározás kiterjeszthető olyan dimenziókra is, amelyek a 2 hatáskörei.

L-rendszer reprezentáció

A Hilbert-görbe L-rendszerrel is elkészíthető  :

Ábécé  : L, R Konstansok  : F, +, - Axióma  : L Szabályok  : L → –RF + LFL + FR− R → + LF - RFR - FL +

Itt F jelentése "előre", + jelentése "balra 90 °" és - jelentése "jobbra 90 °".

Butz egy algoritmust javasol a Hilbert-görbe több dimenzióban történő kiszámítására.

Hivatkozások

1. (de) D. Hilbert , „  Über die stetige Abbildung einer Linie auf ein Flächenstück  ” , Math. Ann. , vol.  38,1891, P.  459–460 ( online olvasás ).
2. Theodore Bially. Térkitöltő görbék: Generálásuk és alkalmazásuk a sávszélesség csökkentésére. IEEE Transactions on Information Theory, IT-15 (6): 658–664, 1969. (Idézi Jonathan Lawder: Techniques for Mapping to and from Space-betöltő görbék , 1999 ,  58. o. ).
3. (in) Heinz-Otto Peitgen  (in) és Dietmar Saupe (szerk.), The Science of Fractal Images , Springer ,2012( online olvasható ) , p.  278.
4. (a) Arthur Butz , "  Alternatív algoritmus Hilbert térkitöltés görbe  " , IEEE Trans. On Computers , vol.  20,1971. április, P.  424-442.

Lásd is

Kapcsolódó cikkek

• Lebesgue görbe
• Peano görbe
• A fraktálok listája Hausdorff dimenzió szerint

Külső linkek

• (en) Eric W. Weisstein , „  Hilbert Curve  ” , a MathWorld- on
• (en) Síkkitöltési görbék a csomóponton