Sierpinski-Dreieck

Grundidee und Konstruktion

Das Sierpinski-Dreieck ist ein 1915 von Wacław Sierpiński beschriebenes Fraktal, also eine geometrische Struktur mit Selbstähnlichkeit auf verschiedenen Größenskalen. Es ist eine Teilmenge eines Dreiecks, das meist gleichseitig gewählt wird; die Konstruktion funktioniert jedoch mit jedem Dreieck.

Der klassische Algorithmus beginnt mit einem Dreieck, dem „Initiator“. Man verbindet die drei Seitenmittelpunkte und zerlegt es dadurch in vier kongruente, zum Ausgangsdreieck ähnliche Teildreiecke. Das mittlere Teildreieck wird entfernt. Auf jedes der drei äußeren Dreiecke werden dieselben Schritte erneut angewandt. So entstehen bei jeder Iteration drei verkleinerte Kopien des vorherigen Musters mit jeweils halber Seitenlänge und einem Viertel seiner Fläche.

Das mathematische Sierpinski-Dreieck ist das Grenzobjekt nach unendlich vielen Iterationen. Praktische Darstellungen benötigen wegen der begrenzten Auflösung von Auge, Bildschirm oder Drucker meist höchstens zehn Iterations- beziehungsweise Rekursionsstufen.

Nach k Schritten bleiben 3^k gleich große Teildreiecke übrig. Im k-ten Schritt werden 3^(k−1) neue Dreiecke entfernt; insgesamt sind dann (3^k−1)/2 Dreiecke entfernt. Einschließlich der verbliebenen Dreiecke wurden insgesamt (3^(k+1)−1)/2 Teildreiecke erzeugt. Beispielsweise bleiben nach vier Schritten 81 Dreiecke übrig, 27 werden in diesem Schritt neu gelöscht und insgesamt sind 40 gelöscht.

Selbstähnlichkeit, Fläche und Dimension

Das Sierpinski-Dreieck ist exakt selbstähnlich und skaleninvariant: Seine drei äußeren Teile sind verkleinerte, genaue Kopien des ganzen Fraktals. Eine passende Vergrößerung eines dreieckigen Teils zeigt daher wieder dieselbe Struktur.

Für ein gleichseitiges Ausgangsdreieck mit Seitenlänge a gilt A₀ = (√3/4)·a². In jedem Schritt bleibt drei Viertel der bisherigen Fläche erhalten. Nach k Schritten beträgt die verbleibende Fläche deshalb A_k = (3/4)^k·(√3/4)·a². Sie verteilt sich auf 3^k Dreiecke mit der Seitenlänge a/2^k. Im k-ten Schritt werden 3^(k−1) Dreiecke dieser Seitenlänge entfernt. Ihre gemeinsame Fläche ist (3/4)^k·(√3/12)·a². Insgesamt wurde nach k Schritten die Fläche (1−(3/4)^k)·(√3/4)·a² entfernt. Für k → ∞ gilt lim A_k = 0. Das Grenzobjekt besitzt somit trotz seiner unendlich vielen Punkte keinen Flächeninhalt im klassischen planimetrischen Sinn.

Die fraktale Dimension beträgt D = log(3)/log(2) = log₂3 ≈ 1,58496. Sie liegt zwischen der Dimension einer Linie und der einer Fläche. Der Wert folgt daraus, dass bei einer Halbierung des Maßstabs drei selbstähnliche Teilstücke entstehen. Das Fraktal ist eng mit der Cantor-Menge verwandt und lässt sich präzise als Durchschnitt aller Zwischenstufen auffassen.

Topologisch ist es ein Unterraum des euklidisch metrisierten ℝ². Es ist dort nirgends dicht, lokal zusammenhängend und ein metrisches Kontinuum.

Weitere Erzeugungsverfahren und mathematische Darstellungen

Als iteriertes Funktionensystem lässt sich das Sierpinski-Dreieck mithilfe des Hutchinson-Operators erzeugen. Drei Ähnlichkeitsabbildungen bilden das gesamte Dreieck jeweils auf eines der drei halb so großen äußeren Teildreiecke ab. Das Sierpinski-Dreieck ist die kompakte Teilmenge der Ebene, die mit der Vereinigung ihrer drei Bilder identisch ist. Bei wiederholter Anwendung geeigneter Transformationen nähern sich auch viele andere Ausgangsfiguren diesem Attraktor, also dem stabilen Grenzobjekt des Prozesses.

Beim „Chaos-Spiel“ zeichnet man ein Dreieck mit den Ecken A, B und C und wählt einen Ausgangspunkt, der sogar außerhalb liegen kann. In jedem Schritt wird zufällig und mit gleicher Wahrscheinlichkeit eine Ecke gewählt. Der nächste Punkt ist der Mittelpunkt zwischen dem bisherigen Punkt und dieser Ecke. Nach sehr vielen Wiederholungen bilden die Punkte das Sierpinski-Dreieck näherungsweise ab. Färbt man sie abhängig von der gewählten Ecke, entstehen drei verschiedenfarbige Teilmuster. Ein erzeugter Punkt gehört genau dann zum Sierpinski-Dreieck, wenn auch der Ausgangspunkt dazu gehört; ein Punkt auf der Strecke AB ist daher ein geeigneter Startpunkt.

Ein Lindenmayer-System beschreibt das Muster mit dem Winkel 120°, dem Startstring A+A+B und den Regeln A → AA sowie B → B+A−B−A+B. In Stephen Wolframs eindimensionalen zellulären Automaten erzeugt außerdem eine einzelne lebende Zelle nach Regel 90 ein Sierpinski-Dreieck.

Die Sierpinski-Pfeilspitzen-Kurve ist eine raumfüllende Kurve, die das Dreieck in der Ebene approximiert. Ihre Selbstähnlichkeit ist wegen Drehungen, Spiegelungen und lokaler Ungenauigkeiten komplizierter. Sierpinski-Kurve, Hilbert-Kurve und Peano-Kurve besitzen andere fraktale Eigenschaften und keinen direkten Zusammenhang mit dem Sierpinski-Dreieck.

Pascalsches Dreieck, Gitter und Graphen

Im Pascalschen Dreieck bilden die Binomialkoeffizienten modulo 2 dasselbe Grundmuster: Ungerade Zahlen entsprechen den übrig gebliebenen, gerade Zahlen den entfernten Teildreiecken. Für ein partielles Pascalsches Dreieck mit 2^k Zeilen ist jedes verbliebene Teildreieck bijektiv einem ungeraden Koeffizienten zugeordnet, also einem Wert mit (a über b) mod 2 = 1. Die entfernten Dreiecke entsprechen – außer in der letzten Iteration – den geraden Koeffizienten mit (a über b) mod 2 = 0; diese Zuordnung ist injektiv, aber nicht bijektiv. Zur effizienten Berechnung genügt zeilenweise binäre Addition modulo 2.

Das regelmäßige Sierpinski-Dreieck hängt außerdem mit dem regelmäßigen Dreiecksgitter zusammen, einer spiegel-, punkt-, dreh- und translationssymmetrischen platonischen Parkettierung der Ebene. Nach k Iterationen überdeckt das Ausgangsdreieck 4^k kleine Gitterdreiecke. Durch affine Abbildungen, die Geraden und Parallelität erhalten, lässt sich diese Beziehung auf beliebige Dreiecke übertragen.

Als ungerichteter Sierpinski-Graph besitzt das Muster für Iterationsschritt k genau E = (3/2)·(3^k+1) Knoten, K = 3^(k+1) Kanten und F = (1/2)·(3^(k+1)+1) Flächen einschließlich der Außenfläche. Der planare und zusammenhängende Graph erfüllt E−K+F = 2. Fast alle Knoten haben Grad 4; nur die drei Außenecken haben Grad 2. Weil alle Grade gerade sind, gibt es Eulerkreise; auch Hamiltonkreise existieren. Die chromatische Zahl ist 3, der chromatische Index 4, und die Flächen lassen sich mit zwei Farben so färben, dass benachbarte Flächen verschiedene Farben haben.

Die entfernten Dreiecke lassen sich außerdem bijektiv den Knoten eines vollständigen ternären Baums mit k+1 Zeilen zuordnen. Dessen Wurzel hat Grad 3, innere Knoten Grad 4 und Blätter Grad 1.

Dreidimensionale und allgemeine Varianten

Das dreidimensionale Gegenstück ist das Sierpinski-Tetraeder. Ausgangsfigur ist ein Tetraeder, aus dessen Mitte in jedem Schritt ein Oktaeder mit halber Kantenlänge entfernt wird. Es bleiben vier Tetraeder, auf die das Verfahren erneut angewandt wird. Nach k Schritten gibt es 4^k Teil-Tetraeder und insgesamt (4^k−1)/3 entfernte Oktaeder unterschiedlicher Größe.

Seine fraktale Dimension ist D = log(4)/log(2) = 2, obwohl das Gebilde im dreidimensionalen Raum liegt. Sein Volumen geht gegen 0. Der Oberflächeninhalt bleibt dagegen konstant: In jedem Schritt vervierfacht sich die Anzahl der dreieckigen Seitenflächen, während ihre Seitenlänge halbiert und ihre einzelne Fläche somit geviertelt wird. Eine Parallelprojektion eines regelmäßigen Sierpinski-Tetraeders auf eine passend ausgerichtete Ebene ergibt eine doppelt belegte quadratische Fläche und macht diese Konstanz anschaulich. Affine Abbildungen verallgemeinern das Ergebnis auf beliebige Tetraeder.

In n Dimensionen beginnt man mit einem n-dimensionalen Simplex. Übrig bleiben n-dimensionale Teil-Simplexe; entfernt werden rektifizierte n-dimensionale Simplexe. Die Überlegungen zu Volumen und Oberflächen lassen sich entsprechend auf n beziehungsweise n−1 Dimensionen übertragen.

Weitere Varianten zerlegen jedes Dreieck statt in 2² = 4 allgemein in m² kongruente Dreiecke. Im zugehörigen Pascalschen Dreieck modulo m entsprechen nicht durch m teilbare Binomialkoeffizienten den verbleibenden Teilen. Auch die Form oder Lage des entfernten Dreiecks kann verändert werden. Als Ausgangsfigur kann sogar ein regelmäßiges oder beliebiges konvexes Polygon dienen, dessen Seitenmittelpunkte wiederholt verbunden werden; die entstehenden Seitenverhältnisse hängen dann von der Ausgangsfigur ab.

Programmierung und Vorkommen

Das Sierpinski-Dreieck kann rekursiv oder iterativ programmiert werden. Bei der rekursiven Umsetzung ruft eine Zeichenfunktion sich für die drei äußeren Teilbereiche mit halber Breite und Höhe erneut auf. Erst bei Erreichen der maximalen Rekursionstiefe werden die Dreiecke gezeichnet. Dieser Code ist kürzer, weil die Punktkoordinaten nicht in Listen oder Arrays gespeichert werden müssen.

Eine iterative Umsetzung berechnet dagegen in jeder Runde aus den vorhandenen Koordinaten die Koordinaten der drei neuen Teildreiecke und speichert sie in neuen Listen. Für gleichseitige Dreiecke wird zur Höhenberechnung der Faktor √3/2 verwendet. Beide Verfahren erzeugen endliche Näherungen des Grenzobjekts.

In der Natur tritt das Muster auf dem Gehäuse der Schneckenart Cymbiola innexa auf.