Triangulierung Polygon mit Loch

Ich habe demnächst eine Prüfung in algorithmischer Geometrie und habe noch einige Übungsaufgaben gefunden, bei denen ich auf die Schnelle keine Lösung weiß.

Die erste Aufgabe, die mich gerade beschäftigt lautet:

Wie kann man ein Polygon mit Löchern triangulieren und wie viele Dreiecke entstehen dann?

Ich habe verschiedene Dreiecke mal ausprobiert und komme auf kein gutes Ergebnis.

So hatte ich zunächst ein Loch im Polygon versucht und kam zB auf:

Polygon-Ecken Loch-Ecken Dreiecke
3 3 6

4 3 7
4 4 8
4 5 9
4 6 10

5 3 8

Ich vermute dass pro Eck eines Loches ein Dreieck mehr hinzukommen wird.

Ohne Loch bestünde die Triangulierung des Vierecks aus 2 Dreieicken.
Ich vermute mal stark einen linearen Zusammenhang:

Meine Vermutung lautet hier erstmal, dass die Anzahl der Dreiecke =
Ecken Polygon + Ecken Loch-Polygon ist.

Mit mehr Löchern kam ich zB auf 12 Dreiecke für ein Viereck mit zwei Dreieckigen Löchern.

Hier weiß ich nicht mehr, wie ich da eine Formel aufstellen könnte.

Wie man die Triangulierung ausführen kann, ist mir ein Rätsel. Ich kenne zwar den "normalen" n log n Sweepline Algorithmus, weiß aber nicht was ich hier abändern müsste, um Löcher zu berücksichtigen.

Bin nun nach vielem Probieren auf die Anzahl der Dreiecke

Polygon-Ecken + 2* #Löcher - 2

gekommen, abr kann es nicht beweisen und weiß auch immer noch nicht iwe ich das konstruieren kann

camper

heidmanns weil schrieb:

Meine Vermutung lautet hier erstmal, dass die Anzahl der Dreiecke =
Ecken Polygon + Ecken Loch-Polygon ist.

Das scheint mir zutreffend zu sein. Beweisskizze könnte ungefähr so aussehen:
1. Klar ist, das jede beliebige minimale Zerlegung in Dreiecke u.a. auch solche Dreicke enthalten muss, die jeweils mindestens 1 Ecke des äußeren (mit M Ecken) und mindestens eine Ecke des inneren (Loch-)Polygons (mit N Ecken) enthalten.
2. Betrachten wir nun eine solche Zerlegung und suchen uns nach Belieben eine Verbindung einer äußeren Ecke mit einer inneren Ecke aus. Verdoppeln wir diesen beiden Ecken so können wir das innere und äußere Polygon in ein (entartetes) Polygon mit M+N+2 Ecken überführen.
3. Die ursprüngliche Aufgabe der Triangulierung ist dann nichts weiter als die normale Triangulierung des erweiterten Polygons, die wir schon kennen.
4. Hat man mehrere Löcher kann man induktiv das Hilfspolygon schrittweise erweitern, so dass man am Ende ein Polygon mit M+Summe_aller_N+2*Anzahl_Löcher hat, entsprechend M+Summe_aller_N+2*Anzahl_Löcher-2 Dreiecke in der Zerlegung.

Jester

Das kann man recht einfach so sehen: man trianguliert einfach alle Facetten durch, auch die äußere, indem man Kurven als Kanten erlaubt. Das ergibt genau 2*Knoten - 4 Facetten (via Eulerformel).

Davon muss man natürlich alle abziehen, die innerhalb eines Lochs und außerhalb liegen. Diese Bereiche sind aber jeweils einfache Polygone, sodass die bekannte Formel für die Facettenzahl zutrifft, nämlich Knoten im Polygon - 2. das gibt insgesamt also #Knoten - 2*#(Anzahl Löcher +1) -- jeder knoten liegt auf genau einem einfachen polygon und die +1 wegen dem äußeren polygon.

Insgesamt haben wir also #Knoten - 2 + 2* #Löcher.

Das kann man recht einfach so sehen: man trianguliert einfach alle Facetten durch, auch die äußere, indem man Kurven als Kanten erlaubt. Das ergibt genau 2*Knoten - 4 Facetten (via Eulerformel).

Kannst du mir das bitte erklären?

Ich glaube, dass ich nicht gaz verstehe, was du meinst und habe noch Probleme mit der äußeren Fläche.

Ich habe jetzt einmal ein Viereck angenommen, ohne Loch.

Wenn ich das trianguliere habe ich 2 innere Facetten und nochmal 4 in der äußeren Fläche sowie einen zusätlichen Knoten, oder?

Also käme ich dann auf: 6 Flächen und 5 Knoten.

Ich habe weiterhin immer noch nur eine Zusammenhangskomponente (ein Tetraeder), und wenn ich mich nicht verzählt habe- 9 Kanten.

Kontrolle:

6 +5 -9 = 2 , scheint zu stimmen

2*Knoten -4 Facetten = 6 = #Dreiecke stimmt auch.

Aber woher kommt die Formel?

V + F - E = 1 + C

ist die einzige Eulerformel, die ich kenne. Aber aus der kann ich die Anzahl der Dreiecke nicht herleiten, oder?

Ich glaube ich habe meinen Denkfehler.

Das Facetten eghört nicht zur Formel, sondern zum umgebenden Satz.

Anzahl Dreiecke in Triangulierung eines Polygons = n-2

Das angewendet auf inneres und äußeres Polygon = 2*(n-2) = 2n -4.

Jester

Du brauchst keinen zusätzlichen Knoten zu, triangulieren, beim Viereck nimmst duneinfach die andere Diagonale und legst sie außen hin.

Euler sagt: n-m+f=2, genau. Bei einer triangulierung gilt 3*f = 2*m (jedes dreieck liegt an drei kanten und jede Kante an zwei dreiecken). Damit kommst du auf das 2n-4.