Tason täyttäviä käyriä

Tason täyttäväksi käyräksi (engl. space-filling curve) sanotaan käyrää, joka kulkee yksikköneliön jokaisen pisteen kautta ja täyttää siinä mielessä koko neliön. Se voi olla hyvin eksoottinen, esimerkiksi äärettömän pitkä, jatkuva, mutta ei derivoituva yhdessäkään pisteessä. Ensimmäinen keksittiin runsaat sata vuotta sitten, myöhemmin monia muita.

Italialainen matemaatikko Giuseppe Peano (1858–1932) keksi vuonna 1890 tason täyttävän käyrän [1]. Hänen lähtökohtansa oli geometrinen. Hän jakoi neliön yhdeksään osaan, joista jokainen määritteli käyrän yhden pisteen. Julkaisussaan hän ei esittänyt päätelmiään kuvina, vaan vain numeerisesti koordinaatteina ja funktioina.  Nykyään on luontevaa esittää käyrän muodostuminen murtoviivalla, joka käy jokaisessa osaneliössä tasan yhden kerran. Neliöruudukossa tämä voidaan tehdä usealla eri tavalla (kuva 1). Ajatus on samankaltainen kuin Königsbergin siltaprobleemassa tai kauppamatkustajan ongelmassa.

Kuva1: murtoviivoja, jotka käyvät neliöruudukon jokaisessa ruudussa tasan yhden kerran [2].

Aloitetaan käyrän piirtäminen neliön lävistäjästä (kuva 2, vasen osakuva). Englanniksi siitä käytetään nimitystä initiator, suomeksi ehkä aloitin. Korvataan se kuvan 1 oikeanpuolimmaisen osakuvan mukaisella murtoviivalla (kuva2, toinen osakuva vasemmalta). Tämä on puolestaan kehitin (engl. generator), joka määrää käyrän muodon. Seuraavaksi neliö jaetaan yhdeksään osaan niin, että kukin osajana on osaneliön lävistäjä, ja korvataan jokainen niistä kehittimen muotoisella murtoviivalla (kuva 2, toinen osakuva oikealta). Jaetaan kukin osaneliö edelleen yhdeksään osaan ja jatketaan jakamista ja korvaamista rajatta. Käyrällä on siten tavallaan fraktaalinkaltainen itsesimilaari rakenne.

Kuva 2: Peanon käyrän konstruointi lähtien yksikköneliön lävistäjästä [3] (vasemmanpuoleinen osakuva), korvataan se murtoviivalla (toinen osakuva vasemmalta), korvataan kukin osajana samanmuotoisella murtoviivalla (kolmas osakuva) ja toimitaan samoin kunkin uuden osajanan kanssa. Huomaa, että jokaisen punaisella rajatun osaneliön sisällä olevat käyrän osat ovat yhdenmuotoiset toisessa osakuvassa näkyvän murtoviivan kanssa.

Tällä kuvakoolla ja murtoviivanleveydellä neliön sisäosa on käytännössä täysin musta jo kuudennen korvauksen jälkeen. Murtoviiva on tällöin 36 = 729 kertaa niin pitkä kuin lävistäjä, sillä pituus kasvaa jokaisella korvauskerralla kolminkertaiseksi. Tästä on kuitenkin vielä pitkä matka tason täyttävään Peanon käyrään, joka saadaan, kun menettelyä jatketaan rajatta. Lopputuloksena saatava käyrä on luonnollisesti äärettömän pitkä. Ei ole itsestään selvää, millainen objekti se on. Sen Hausdorff-dimensio [4] on $$D=   \frac{log(9)}{log(3)} = 2$$

missä 3 saadaan aloittimen jakosuhteesta ja 9 kehittimen osajanojen lukumäärästä. Tulos viittaa siihen, että lopputulosta olisi pidettävä mieluummin pintana kuin käyränä. Tämä tuntuisi luonnolliselta, koska käyrä täyttää koko yksikköneliön. Kyseessä on kuitenkin käyrä eikä kuvio niin kuin nähdään myöhemmin tämän jutun loppupuolella!

Peanon käyriksi nimitetään muitakin kuvassa 1 näkyvien kehittimien muodostamia käyriä [5].

Hilbert, Phelps ja Kim

Toista sataa vuotta ikää on myös Hilbertin käyrällä (kuva 3)[6]. Sen keksi saksalainen matemaatikko David HIlbert (1862–1943) vuonna 1891. Sitä voidaan pitää Peanon käyrän muunnoksena, sillä rakentumisperiaate on samantapainen. Nyt neliö jaetaan vain neljään osaan. Äärettömän monen toistokerran jälkeen lopputuloksena saatavan käyrän Hausdorff-dimensio on samoin 2, koska sekin täyttää tason. Tämä merkitsee sitä, että Peanon ja Hilbertin käyrät eivät ole fraktaaleja, koska niiden dimensio on kokonaisluku.

Kuva 3: Hilbertin käyrän kehitin (vasen osakuva) ja ensimmäisiä korvausvaiheita.

Peanon kohdalla ajatus tason täyttävästä käyrästä oli uusi oivallus. Jotain kiinnostavaa uutuutta siinä tosiaan lienee aikanaan ollut, koska Hilbertkin tarttui siihen välittömästi. Myöhemmin on määritelty paljon muita tason täyttäviä käyriä. Nykyään tason täyttävän käyrän piirtämistä pidetään helppona [7].  Sitä se onkin sekä geometrisen rakenteen keksimisen että erityisesti käyrän piirtämisen mielessä, koska piirtämiseen voidaan käyttää graafisia matematiikkaohjelmia. Tästä ovat esimerkkeinä muiden muassa amerikkalaisen Steve Phelpsin [8] ja korealaisen Kyeong Yong Kimin [9] Geogebra-materiaaleissa julkaisemat käyrät tältä vuosituhannelta (kuva 4).

Kuva 4: Steve Phelpsin (ylärivi) ja Kyeong Yong Kimin (alarivi) keksimien tason täyttävien käyrien ensimmäisiä iteraatioita.

Objekti ja sovelluksia

Tason täyttävän käyrän muodostumisesta saa hyvä kuvan jo muutaman ensimmäisen korvausvaiheen perusteella. Todellisuudessa todellista äärettömän pitkää käyrää ei voida piirtää näytölle eikä paperille, koska se syntyy vasta toistamalla korvaussääntöä rajatta. Ja jos voitaisiinkin, niin kuva näyttäisi kaikissa suurennoksissa neliöltä, jonka sisäosa on väritetty kokonaan, koska käyrä käy läpi kaikki neliön pisteet. Kuva ei näytä siis millään tavalla kiinnostavalta.

Visuaalisen mielikuvan ei pidä kuitenkaan antaa harhauttaa, sillä lopputulos ei ole tasoneliö, vaan täydellinen hyvinmääritelty käyrä [7].  On mahdollista määrittää laskemalla minkä tahansa pisteen paikka käyrällä. Neliön jakaminen yhä pienempiin osiin määrittelee kaikissa osavaiheissa äärellisen määrän pisteitä, jotka voidaan numeroida ja yhdistää murtoviivalla esimerkiksi Hilbertin käyrän muodostamisen tapaan [10] (kuva 5). Lopputuloksessa käyrällä on ääretön määrä pisteitä, sillä se käy läpi kaikki yksikköneliön pisteet. Niitä ei voi enää numeroida, koska määrä on ylinumeroituva. Älyllinen haaste on sen ymmärtämisessä, miten käyrä murtautuu rajankäynnissä ulos äärellisyyden ja jopa numeroituvuuden kahleista.

Kuva 5: Hilbertin käyrän piirtämisen kolme ensimmäistä vaihetta. Kukin osaneliö määrittää yhden pisteen.

Ensikatsannolta teoreettisilta tuntuvien, tason täyttävien käyrien tutkimuksen synnyttämille ideoille on keksitty ehkä vähän yllättäen käytännön sovelluksia hyvinkin erilaisilla alueilla, esimerkiksi ruokakaupan kotitoimitusten jakelureitin suunnittelu, värin säästäminen lasertulostuksessa ja suuraineistojen datan ryhmittely suurten matriisien kertolaskujen tehostamiseksi [7]. Hupipuolelle on kuitenkin ehkä laskettava käyrien muuntaminen kuunneltavaksi musiikiksi [11].

Lähteitä ja lisää luettavaa:

[1] Peano, Giuseppe (1890): Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen, 36 (1): 157–160.

[2] Yang, Guangjun; Yang, Xiaoling ja Wang, Ping (2019): Arithmetic-Analytic Representation of Peano Curve. Hindawi, Open Access Magazine, osoitteessa https://www.hindawi.com/journals/ijmms/2019/6745202/

[3] Logo Arts, Peano Curve – plane filling curve osoitteessa http://www.cr31.co.uk/logoarts/prog/plane/peano.html Koodin rakenne perustuu sivustolla esitettyyn koodiin, vaikka kuvat onkin piirretty FMS-Logolla. Sivustolla käytetyssä XLogossa on omalaatuisia piirteitä, joten koodi ei toimi sellaisenaan tavallisemmissa Logo-versioissa.

[4] Fractals and the Fractal Dimension osoitteessa https://www.vanderbilt.edu/AnS/psychology/cogsci/chaos/workshop/Fractals.html

[5] Mac Tutor: Peano’s Space-filling Curve osoitteessa https://mathshistory.st-andrews.ac.uk/Extras/Peano_curve/

[6] Space-filling curve osoitteessa https://en.wikipedia.org/wiki/Space-filling_curve

[7] Hayes, Brian: Crinkly Curves. American Scientist, May–June 2013, vol. 101 (3) osoitteessa https://www.americanscientist.org/article/crinkly-curves

[8] Phelps, Steve: Space-filling curve osoitteessa https://www.geogebra.org/m/ehwzw29p

[9] Kim, Kyeong Yong (2015): Space-filling curve osoitteessa https://www.geogebra.org/material/show/id/XZe8ES5s

[10] The Hilbert Curve. Constructing the Hilbert Curve. Mapping Points on a Line to Points in a Square osoitteessa http://bit-player.org/extras/hilbert/

[11] Haverkort, Herman: The sound of space-filling curves, examples osoitteessa http://herman.haverkort.net/?id=sound_of_space-filling_curves#proximity_mapping


Tilaa Dimension uutiskirje – saat sähköpostiisi aina kuunvaihteessa koosteen tuoreimmista artikkeleista

Kirjoittaja