Krzywe wypełniające przestrzeń wyjaśnione

Linia jest jednowymiarowa, a kwadrat dwuwymiarowy, więc wydaje się oczywiste, że linia nigdy nie pokryje kwadratu. W 1890 roku Giuseppe Peano pokazał, że to możliwe: istnieje krzywa ciągła, która przechodzi przez każdy punkt kwadratu. Odkrycie to zmusiło matematyków do ponownego przemyślenia, czym są krzywa i wymiar, a sto lat później te same krzywe utrzymują w komputerach porządek w danych map i obrazów.

Krzywa Hilberta poziomu 5 w siatce 32 na 32 komórki, pokolorowana od początku do końca
Krzywa Hilberta poziomu 5 w siatce 32 na 32 komórki, pokolorowana od początku do końca

Tyle samo punktów co kwadrat

W 1877 roku Georg Cantor udowodnił, że odcinek ma dokładnie tyle samo punktów co kwadrat: każdy punkt kwadratu można połączyć w parę z jego własnym punktem linii. Do Richarda Dedekinda napisał: „Widzę to, ale w to nie wierzę”. Przyporządkowanie Cantora skacze jednak bezładnie; rozrywa linię w pył. Otwarte pozostawało pytanie, czy linia może pokryć kwadrat bez rozrywania, czyli w sposób ciągły.

Portret Georga Cantora
Portret Georga Cantora

Krzywa Peana

W 1890 roku włoski matematyk Giuseppe Peano dał odpowiedź: tak. Opisał, samymi wzorami i bez ani jednego rysunku, krzywą ciągłą, która przechodzi przez każdy punkt kwadratu jednostkowego. Jego konstrukcja dzieli kwadrat na 9 mniejszych kwadratów, przechodzi przez nie zagięciami w kształcie litery S i powtarza to wewnątrz każdego z nich, raz za razem.

Rysunek Hilberta

Rok później David Hilbert opublikował prostszą wersję, z rysunkiem, który uwidocznił całą ideę. Podziel kwadrat na 4 części i połącz ich środki jedną zagiętą linią. Następnie podziel każdy mały kwadrat na 4 i zrób to jeszcze raz, obracając małe kopie tak, żeby linia przechodziła z jednej do następnej. Krzywa poziomu n odwiedza 4ⁿ komórek; kwadrat wypełnia dopiero granica wszystkich poziomów. W 1900 roku Eliakim Hastings Moore podał wariant, który kończy się tam, gdzie się zaczyna: zamkniętą pętlę.

Dlaczego przejście do granicy działa

Prześledź jeden punkt linii, na przykład ten leżący w jednej trzeciej jej długości. Na poziomie 1 leży on w jednej z 4 komórek. Na każdym następnym poziomie przesuwa się, ale pozostaje wewnątrz tej komórki, potem wewnątrz jej ćwiartki i tak dalej: wewnątrz komórki, której bok za każdym razem zmniejsza się o połowę. Jego położenie więc się ustala i to samo dotyczy każdego punktu linii. Granicą jest krzywa ciągła. A ponieważ każdy poziom odwiedza każdą komórkę coraz gęstszej siatki, krzywa graniczna zbliża się dowolnie blisko do każdego punktu kwadratu i, jako ciągła, do niego dociera.

Nie da się tego zrobić różnowartościowo

Krzywa wypełniająca przestrzeń musi zapłacić pewną cenę. W 1879 roku Eugen Netto udowodnił, że linii nie da się odwzorować na kwadrat w sposób jednocześnie ciągły i różnowartościowy. Krzywa musi więc przechodzić przez niektóre punkty więcej niż raz; krzywa Hilberta dotyka niektórych punktów nawet cztery razy. Nigdzie nie jest też gładka: w żadnym punkcie nie ma stycznej.

Długość i wymiar

Poziom n krzywej Hilberta jest 2ⁿ − 2⁻ⁿ razy dłuższy od boku kwadratu, czyli mniej więcej dwa razy dłuższy od poprzedniego poziomu. Długość rośnie nieograniczenie, a mimo to krzywa nigdy nie opuszcza kwadratu. Krzywa złożona z 4 kopii samej siebie o połowę mniejszych ma wymiar log 4 / log 2 = 2, czyli wymiar kwadratu, który wypełnia. Krzywa Peana składa się z 9 kopii w skali jednej trzeciej: również log 9 / log 3 = 2.

Zachowanie sąsiedztwa

Krzywa Hilberta ma własność, która czyni ją użyteczną: punkty leżące blisko siebie na linii trafiają blisko siebie także w kwadracie. Odwrotna zależność nie zawsze może zachodzić: dwie sąsiednie komórki mogą być na linii daleko od siebie. Komputery używają tej krzywej do zapisywania danych dwuwymiarowych, takich jak kafelki map, piksele czy miejsca na kuli ziemskiej, w jednowymiarowym porządku, w którym większość sąsiadów pozostaje blisko siebie. Porządek Z, opisany w 1966 roku przez Guya Mortona z IBM, robi to samo, przeplatając bity obu współrzędnych. Oblicza się go szybciej, ale gorzej zachowuje sąsiedztwo, bo skacze.

Flowsnake Gospera i grot strzały Sierpińskiego

Nie każda krzywa wypełniająca przestrzeń wypełnia kwadrat. Krzywa Billa Gospera z 1973 roku, znana jako flowsnake, odkąd w 1976 roku napisał o niej Martin Gardner, biegnie po siatce trójkątów, a każdy odcinek zastępuje siedmioma. Wypełnia wyspę Gospera, kształt o fraktalnym wybrzeżu: siedem jej kopii składa się w większą wyspę. Krzywa Wacława Sierpińskiego zwana grotem strzały na pierwszy rzut oka wygląda podobnie, ale ma tylko trzy kawałki na odcinek, o połowę krótsze, i dlatego niczego nie wypełnia: kreśli trójkąt Sierpińskiego, o wymiarze log 3 / log 2 ≈ 1,585.

Portret Wacława Sierpińskiego
Portret Wacława Sierpińskiego

Wypróbuj

Otwórz eksplorator krzywych wypełniających przestrzeń i naciśnij „Odtwórz”, aby zobaczyć, jak pisak rysuje każdy poziom krzywej Hilberta od początku do końca. Przełącz na zagięcia Peana w kształcie litery S, zamkniętą pętlę Moore'a, skaczący porządek Z, flowsnake Gospera i grot strzały. Ustaw pisak w dowolnym miejscu krzywej albo osi liczbowej pod rysunkiem, aby zobaczyć, który krok trafia do której komórki, i pokaż poprzedni poziom, aby zobaczyć, jak każdy krok zamienia się w całe zagięcie.

Często zadawane pytania

Kto odkrył pierwszą krzywą wypełniającą przestrzeń?

Giuseppe Peano, w 1890 roku. Dlatego krzywe wypełniające przestrzeń nazywa się też krzywymi Peana. Krzywa Davida Hilberta z 1891 roku jest najbardziej znana, bo Hilbert jako pierwszy przedstawił konstrukcję na rysunku.

Czy krzywa wypełniająca przestrzeń jest fraktalem?

Jest zbudowana jak fraktal: z mniejszych kopii samej siebie. Ale jej wymiar fraktalny wynosi 2, czyli jest liczbą całkowitą, ponieważ gotowa krzywa pokrywa obszar. Grot strzały Sierpińskiego, o wymiarze około 1,585, jest fraktalem w zwykłym sensie.

Jak długa jest krzywa Hilberta?

Poziom n jest 2ⁿ − 2⁻ⁿ razy dłuższy od boku kwadratu: na poziomie 1 to 1,5, na poziomie 4 już 15,94, a na poziomie 8 prawie 256. Krzywa graniczna jest nieskończenie długa.

Ile poziomów potrafi narysować eksplorator?

Do 8 poziomów dla krzywej Hilberta, krzywej Moore'a i porządku Z, co daje siatkę 256 na 256 komórek; 5 dla krzywej Peana (243 na 243 komórki) i krzywej Gospera (16 807 odcinków); oraz 10 dla grotu strzały Sierpińskiego (59 049 odcinków).

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Otwórz eksplorator krzywych wypełniających przestrzeń