Rumudfyldende kurver – med anvendelser!

Det er gået op for mig, at rumopfyldende kurver – space filling curves i min oversættelse – har anvendelser. Til lagring af data. Her troede jeg, at det var noget, matematikerne kunne have for sig selv, men nej. Det skal da på bloggen.
Man skulle ikke tro, at det er muligt at lave en kurve, som går igennem hvert eneste punkt i et kvadrat i planen, men det er det. Og man kan såmænd også fylde hele planen eller hele rummet eller hele det 17-dimensionale rum Det gav i slutningen af 1800-tallet anledning til, at man måtte skærpe definitioner og ideer om bl.a. kontinuitet. Hvordan ser sådan en kurve mon ud? Tegner man kurven ind, får man malet hele planen, så der må en anden forklaring til og andre illustrationer.

Her er Hilbertkurven:

(Illustration, Byron Mayfield, Wikimedia Commons) Som man kan se, fremkommer kurven som en grænse – kurverne bliver tættere og tættere – rammer flere og flere punkter –  og man må vise, at der faktisk er en grænsekurve – at det giver mening, at denne grænsekurve er kontinuert og at den går igennem ethvert punkt i kvadratet. Der er mange eksempler på rumudfyldende kurver. De kaldes også Peanokurver, fordi Giuseppe Peano gav det første eksempel på en. Jeg holder mig til Hilbertkurven. Her er de første 6 kurver i den følge af kurver, som i grænsen er Hilbertkurven – drejet i forhold til illustrationen ovenfor.

(Billede fra Wikipedia) En beskrivelse af den iterative proces er som følger (leg med det her): 1) Del kvadratet op i fire og lav en kurve mellem centrene bestående af tre linjestykker som i første billede. 2) Opdel hvert af de fire kvadrater i fire, hvor kurven fra step 1 tegnes ind. Nu har vi fire mindre versioner af kurven fra step 1. Kald dem Sydvest, Nordvest,  Nordøst, Sydøst. Roter det syd-vestlige kvadrat 90 grader med uret. Roter det sydøstlige kvadrat 90 grader mod uret. Forbind nu de fra SØ til NØ og fra SV til NV. 3) gentag manøvren i mindre og mindre kvadrater. Se en mere præcis forklaring nedenfor, men lad mig lige sparke anvendelsen ind først: Har man data med to koordinater og vil søge i dem, er det (som jeg forstår det) nyttigt at omsætte til dimension 1, altså at ordne punkterne med 2 koordinater. Det kan man gøre på mange måder, men gør man det ved at følge en passende iteration på vejen til eksempelvis en Hilbertkurve (dem vil jeg også kalde Hilbertkurver nedenfor, selvom det egentlig kun er grænsekurven, der er en Hilbertkurve), så får man følgende sidegevinst:

Punkter, som ligger tæt på hinanden, når man måler langs kurven, ligger også tæt på hinanden i kvadratet. OBS: Ikke omvendt. Det skyldes den iterative konstruktion – man ændrer kurven lokalt, når man laver en iteration mere. Billedet nedenfor er en afbildning af regnbuens farver ordnet langs linjen ind i planen med en Hilbertkurve. Bemærk, at der er bratte overgange svarende til skift af kvadrater (mellem rød og gul for eksempel), men alt med sammen farve er tæt på noget med samme farve.

 

En anden beskrivelse af kurven i iteration nummer n, altså en kontinuert afbildning f_n:[0,1]\to [0,1]^2 fås ved at fortælle hvilken rækkefølge, kurven går igennem centrum for kvadraterne. De første fire centre nummereres 1,2,3,4 fra nederste venstre center og med uret – SV, NV, NØ, SØ med beskrivelsen ovenfor. Brug intervallet [ (k-1)4^{-n},k\,4^{-n}[ til at give kurven i kvadrat nummer k for kurven f_n.

Den n+1’ste nummerering laves ud fra den n’te som følger: Der er 4^{n+1} kvadrater grupperet med 4^n i hhv. SV, NV, NØ, SØ.

Start i SV. Brug ordenen fra step n – roter 90 grader med uret og brug den omvendte orden. I NV bruges ordenen fra step n, men man begynder med nummer 4^n +1. I NØ bruges igen ordenen fra step n, men begynd med nummer 2\cdot 4^n +1. I SØ nummereres med orden fra step n, der roteres 90 grader mod uret og nummerordenen vendes om – og man lægger 3\cdot 4^n til.

Observer, at både f_n og f_{n+1} afbilder [ (k-1)4^{-n},k\,4^{-n}[ til samme kvadrat – med sidelængde 2^n. Altså er |f_n(x)-f_{n+1}(x)|< 2^n for alle x. Det kan man bruge til at se, at f_n er en Cauchyfølge mht. supremumsafstanden – altså konvergerer følgen og grænsefunktionen er kontinuert. At grænsekurven går igennem alle punkter viser man ved, at der for hvert punkt p\in I^2 og hvert \varepsilon er et punkt på kurven i højst afstand \varepsilon. Brug nu, at I er kompakt, så f(I) er lukket til at konkludere, at p\in f(I).

Vi skal da have en XKCD ind her: Fra IP-adresser – altså noget data på en linje – til et kvadrat via en Hilbertkurve:

Map of the Internet