Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Triangulation. Aufstellen aller möglichen Punktefolgen
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Triangulation. Aufstellen aller möglichen Punktefolgen
Wario
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 01.05.2020
Mitteilungen: 117
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-09-28 21:00


Beispiel ($n=4$): Ein konvexes $4$-Eck habe die Ecken $1,2,3,4$.
Dann besteht eine Füllung mit nichtüberschneidenen Dreiecken (Triangulation) aus $n-2=4-2=2=:k$ Dreiecken.
Insgesamt gibt es $
\dfrac{1}{k+1}\dbinom{2k}{k}=\dfrac{1}{3}\dbinom{4}{2}=2$ verschiedene Triangulationen, das sind:
$
\begin{cases}
\Delta_1: 1-2-3 \\ \Delta_2: 1-3-4
\end{cases}$  oder  $
\begin{cases}
\Delta_1: 1-2-4  \\  \Delta_2: 2-3-4
\end{cases}$


Wie kann ich die Punktefolgen für beliebige $n$ effizient ermitteln?

Siehe auch wikipedia oder wikipedia (en) oder Skript.



Beim 5-Eck sind es:
1-2-3
1-3-4
1-4-5
 
1-4-5
1-2-4
2-3-4
 
1-2-3
1-3-5
3-4-5
 
1-2-5
2-4-5
2-3-4
 
1-2-5
2-3-5
4-3-5



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4729
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-09-28 23:52


sollte deine Frage beantworten (insbesondere der Abschnitt 3.4).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 01.05.2020
Mitteilungen: 117
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-09-29 04:29


> (insbesondere der Abschnitt 3.4).

Ja?

>
> sollte deine Frage beantworten

Das steckt da sicher irgendwie drin. Aber ich interessiere mich ja für die konkreten Punktefolgen, nicht für die Anzahlformel.

Die Seite kenne ich schon (vergessen zu erwähnen); ich sehe nicht wie mir dieser allgemeine Link zu einem Teilaspekt davon hier weiterhilft.


Für die Triangulation bei einer festgehaltenen Ecke x=1,2,..,n  eines n-Ecks komme ich auf die Zahlenfolge

x --  1 + (x-1+i mod n) -- 1 + (x+i mod n)   für i=1,...,n-2

Zum Beispiel
3-4-5
3-5-1
3-1-2

beim 5-Eck.


Ich möchte wissen, wie ich alle Punktefolgen für alle verschiedenen Triagulationen erhalte.
 




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4729
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-09-29 12:10


Eine kombinatorisch bewiesene Rekursionsformel für die Catalan-Zahlen liefert dir eine rekursive Bildungsvorschrift für die Triangulierungen. Daher wird dir Abschnitt 3.4 weiterhelfen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 01.05.2020
Mitteilungen: 117
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-09-29 20:24


2020-09-29 12:10 - Triceratops in Beitrag No. 3 schreibt:
Eine kombinatorisch bewiesene Rekursionsformel für die Catalan-Zahlen liefert dir eine rekursive Bildungsvorschrift für die Triangulierungen. Daher wird dir Abschnitt 3.4 weiterhelfen.

Diese Abschnitt lautet

https://en.wikipedia.org/wiki/Catalan_number schreibt:

=== Fourth proof ===

This proof uses the triangulation definition of Catalan numbers to establish a relation between Cn and Cn+1.  Given a polygon P with n + 2 sides, first mark one of its sides as the base.  If P is then triangulated, we can further choose and orient one of its 2n + 1 edges.  There are (4n + 2)Cn such decorated triangulations.  Now given a polygon Q with n + 3 sides, again mark one of its sides as the base.  If Q is triangulated, we can further mark one of the sides other than the base side.  There are (n + 2)Cn + 1 such decorated triangulations.  Then there is a simple bijection between these two kinds of decorated triangulations:  We can either collapse the triangle in Q whose side is marked, or in reverse expand the oriented edge in P to a triangle and mark its new side.  Thus
<math>(4n+2)C_n = (n+2)C_{n+1}.</math>
The binomial formula for Cn follows immediately from this relation and the initial condition C1 = 1.



Wenn Du da für Zerlegungsdreiecke p -- q -- r sofort Formeln p, q, r raussehen kannst, die dann evtl. Catalan-Zahlen beinhalten; ich kann es nicht.

Es scheint irgendwie über Diagonalen zu gehen (vielleicht die Methode oder eine weitere Methode). Also entweder Du zeigst konkret, was Du meinst. Ansonsten kann ich Deinen Link nicht verwenden, muss ihn evtl. sogar als irreführend ansehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4729
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-09-29 20:32


2020-09-29 20:24 - Wario in Beitrag No. 4 schreibt:
Wenn Du da für Zerlegungsdreiecke p -- q -- r sofort Formeln p, q, r raussehen kannst, die dann evtl. Catalan-Zahlen beinhalten; ich kann es nicht.

Das habe ich nicht behauptet. Ich habe gesagt, dass du daraus (wenn du den Beweis wirklich verstanden hast) eine rekursive Bildungsvorschrift ableiten kannst.

Sprich: ausgehend von allen Triangulierungen des n-Ecks bekommst du eine Liste aller Triangulierungen des (n+1)-Ecks.

Natürlich ist noch etwas Arbeit zu tun. Man muss nämlich das "Teilen durch n+2" in der Rekursionsformel kombinatorisch deuten. Aber ich will nicht zu viel verraten.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 01.05.2020
Mitteilungen: 117
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-09-29 22:00


2020-09-29 20:24 - Wario in Beitrag No. 4 schreibt:
 Zerlegungsdreiecke p -- q -- r
Formeln p, q, r

2020-09-29 20:32 - Triceratops in Beitrag No. 5 schreibt:
Das habe ich nicht behauptet. Ich habe gesagt, dass du daraus (wenn du den Beweis wirklich verstanden hast) eine rekursive Bildungsvorschrift ableiten kannst.

Sprich: ausgehend von allen Triangulierungen des n-Ecks bekommst du eine Liste aller Triangulierungen des (n+1)-Ecks.

Da weiß ich nicht wie das geht bzw. wie der Ansatz ist.


2020-09-29 20:32 - Triceratops in Beitrag No. 5 schreibt:
Man muss nämlich das "Teilen durch n+2" in der Rekursionsformel kombinatorisch deuten. Aber ich will nicht zu viel verraten.

Das ist klar, dass man das machen muss. Aber beim letzten Satz weiß ich nicht, wie ich das verstehen soll. Es klingt, überspitzt gesagt, als wollest Du hier ein Spiel spielen. Das ist nicht hilfreich. Wenn Du etwas weißt oder glaubst zu wissen, sprich es offen aus oder behalte es als Geheimwissen für Dich; es besteht ja auch keine Verpflichtung.
Also ggf. Ansatz zeigen oder einfachen Sonderfall (5-Eck) vorrechnen oder...


Wie auch immer:
Ich habe einen Asatz, der vermutlich zum Richtigen führt. (Ob das der gleiche ist, wie mit Catalan weiß ich nicht.)


Ansatz am Beispiel des 5-Ecks (n=5): Eine Triangulation besteht aus aus n-3 = 2 Diagonalen.

Von der Ecke 1 ausgehend sind die Diagonalenpaare mit den kleinsten Nummern, die jeweils eine (verschiedene) Triangulation bilden:
1-3, 1-4
1-4, 2-4
2-4, 2-5
2-5, 3-5
3-5, 1-3


Damit bekommt man die Cn-2 =C3 = 5 (verschiedenen) Triangulationen
1-3-2
1-3-4
1-4-5

1-4-2
1-4-5
2-4-3

2-4-3
2-4-5
2-5-1

2-5-1
2-5-4
3-5-2

3-5-1
3-5-4
1-3-2


Hier ist mir im Augenblick noch das Bildungsgesetz der letzten Nummern unklar.


Nichtsdestotrotz wären auch
2020-09-29 20:24 - Wario in Beitrag No. 4 schreibt:
explizite Formeln p, q, r
für Zerlegungsdreiecke p -- q -- r
interessant.  



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]