Rymdfyllande kurvor förklarade
En linje är endimensionell och en kvadrat tvådimensionell, så det verkar självklart att en linje aldrig kan täcka en kvadrat. År 1890 visade Giuseppe Peano att den kan det: det finns en kontinuerlig kurva som går genom varje punkt i en kvadrat. Upptäckten tvingade matematikerna att tänka om kring vad en kurva och en dimension är, och ett århundrade senare håller samma kurvor ordning på data från kartor och bilder inne i datorer.
Lika många punkter som en kvadrat
År 1877 bevisade Georg Cantor att en sträcka har exakt lika många punkter som en kvadrat: varje punkt i kvadraten kan paras ihop med en egen punkt på linjen. Han skrev till Richard Dedekind: ”Jag ser det, men jag tror det inte.” Cantors ihopparning hoppar dock vilt omkring; den sliter sönder linjen till stoft. Den öppna frågan var om en linje kunde täcka en kvadrat utan att slitas sönder, det vill säga kontinuerligt.
Peanos kurva
År 1890 gav den italienske matematikern Giuseppe Peano svaret: ja. Han beskrev, enbart med formler och utan en enda bild, en kontinuerlig kurva som går genom varje punkt i enhetskvadraten. Hans konstruktion delar kvadraten i 9 mindre kvadrater, går genom dem i S-böjar och upprepar detta inuti var och en av dem, om och om igen.
Hilberts bild
Ett år senare publicerade David Hilbert en enklare version, med den bild som gjorde idén synlig. Dela kvadraten i 4 och förbind mittpunkterna med en enda böjd linje. Dela sedan varje liten kvadrat i 4 och gör om det, och vrid de små kopiorna så att linjen löper vidare från den ena till nästa. Kurvan av nivå n besöker 4ⁿ celler; det som fyller kvadraten är gränsvärdet av alla nivåer. År 1900 angav Eliakim Hastings Moore en variant som slutar där den börjar, en sluten slinga.
Varför gränsvärdet fungerar
Följ en punkt på linjen, till exempel den som ligger en tredjedel av vägen. På nivå 1 ligger den i en av de 4 cellerna. På varje följande nivå flyttar den sig, men den stannar inom den cellen, och sedan inom en fjärdedel av den, och så vidare: inom en cell vars sida halveras varje gång. Dess läge kommer alltså till ro, och detsamma gäller för varje punkt på linjen. Gränsvärdet är en kontinuerlig kurva. Och eftersom varje nivå besöker varje cell i ett allt finare rutnät kommer gränskurvan godtyckligt nära varje punkt i kvadraten och når den också, eftersom den är kontinuerlig.
Det går inte ett-till-ett
En rymdfyllande kurva måste betala ett pris. År 1879 bevisade Eugen Netto att en linje inte kan avbildas på en kvadrat kontinuerligt och ett-till-ett på samma gång. Kurvan måste alltså gå genom vissa punkter mer än en gång; Hilbertkurvan rör vid vissa punkter upp till fyra gånger. Den är inte heller slät någonstans: den har ingen tangent i någon punkt.
Längd och dimension
Nivå n av Hilbertkurvan är 2ⁿ − 2⁻ⁿ gånger så lång som kvadratens sida, ungefär dubbelt så lång som nivån före. Längden växer över alla gränser, och ändå lämnar kurvan aldrig kvadraten. En kurva som består av 4 kopior av sig själv i halv storlek har dimensionen log 4 / log 2 = 2, dimensionen hos den kvadrat som den fyller. Peanokurvan har 9 kopior i en tredjedels storlek: också log 9 / log 3 = 2.
Att hålla ihop grannar
Hilbertkurvan har en egenskap som gör den användbar: punkter som ligger nära varandra på linjen hamnar nära varandra i kvadraten. Det omvända kan inte alltid gälla: två grannceller kan ligga långt ifrån varandra på linjen. Datorer använder kurvan för att lagra tvådimensionella data, till exempel kartrutor, pixlar eller platser på jordklotet, i en endimensionell ordning som håller de flesta grannar nära varandra. Z-ordningen, som Guy Morton beskrev på IBM 1966, gör samma jobb genom att fläta samman de två koordinaternas bitar. Den går snabbare att beräkna, men den håller ihop grannar sämre, eftersom den hoppar.
Gospers flowsnake och Sierpińskis pilspets
Inte alla rymdfyllande kurvor fyller en kvadrat. Bill Gospers kurva från 1973, känd som flowsnake sedan Martin Gardner skrev om den 1976, löper över ett nät av trianglar med sju segment för varje enskilt. Den fyller Gosperön, en form med fraktal kustlinje, där sju kopior passar ihop till en större. Wacław Sierpińskis pilspetskurva ser snarlik ut vid första anblicken, men den har bara tre delar per segment i halv storlek och fyller därför ingenting: den ritar upp Sierpińskitriangeln, som har dimensionen log 3 / log 2 ≈ 1,585.
Utforska den
Öppna utforskaren för rymdfyllande kurvor och tryck på ”Spela” för att se en penna rita varje nivå av Hilbertkurvan från början till slut. Byt till Peanos S-böjar, Moores slutna slinga, den hoppande Z-ordningen, Gospers flowsnake och pilspetsen. Sätt pennan var som helst på kurvan, eller på tallinjen under bilden, för att se vilket steg som hamnar i vilken cell, och slå på ”Visa föregående nivå” för att se hur varje steg blir till en hel böj.
Ofta ställda frågor
Vem upptäckte den första rymdfyllande kurvan?
Giuseppe Peano, år 1890. Därför kallas rymdfyllande kurvor också Peanokurvor. David Hilberts kurva från 1891 är den mest kända, eftersom Hilbert var den förste som ritade en bild av konstruktionen.
Är en rymdfyllande kurva en fraktal?
Den är uppbyggd som en, av mindre kopior av sig själv. Men dess fraktala dimension är 2, ett heltal, eftersom den färdiga kurvan täcker en yta. Sierpińskis pilspetskurva, med en dimension på ungefär 1,585, är en fraktal i vanlig mening.
Hur lång är Hilbertkurvan?
Nivå n är 2ⁿ − 2⁻ⁿ gånger kvadratens sida: 1,5 på nivå 1, 15,94 på nivå 4 och nästan 256 på nivå 8. Gränskurvan är oändligt lång.
Hur många nivåer kan utforskaren rita?
Upp till 8 nivåer för Hilbertkurvan, Moorekurvan och Z-ordningen, vilket är ett rutnät med 256 gånger 256 celler; 5 för Peanokurvan (243 gånger 243 celler) och Gosperkurvan (16 807 segment); och 10 för Sierpińskis pilspets (59 049 segment).
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Öppna utforskaren för rymdfyllande kurvor