„Triangulation (Punktemenge)“ – Versionsunterschied
| [ungesichtete Version] | [ungesichtete Version] |
Inhalt gelöscht Inhalt hinzugefügt
EvaK (Diskussion | Beiträge) +Unverständlich |
Keine Bearbeitungszusammenfassung |
||
| Zeile 3: | Zeile 3: | ||
Eine Triangulation einer Menge von Punkten '''P''' in der Ebene ist ein |
Eine Triangulation einer Menge von Punkten '''P''' in der Ebene ist ein |
||
[[Planarer Graph|ebener]] [[Dreiecksgraph]], dessen Knoten genau die Punkte aus '''P''' sind. |
|||
Alle inneren Gebiete einer Triangulierung sind Dreiecke, während das äußere Gebiet |
Alle inneren Gebiete einer Triangulierung sind Dreiecke, während das äußere Gebiet |
||
von der konvexen Hülle von '''P''' begrenzt wird. |
von der konvexen Hülle von '''P''' begrenzt wird. |
||
| Zeile 10: | Zeile 10: | ||
die '''n-2'''-te [[Catalan-Zahl]], wobei '''n''' die Kardinalität von '''P''' bezeichnet. |
die '''n-2'''-te [[Catalan-Zahl]], wobei '''n''' die Kardinalität von '''P''' bezeichnet. |
||
Oft ist man daran interessiert, eine Triangulation mit besonderen |
Oft ist man daran interessiert, eine Triangulation mit besonderen Eigenschaften zu berechnen. Zum Beispiel gibt |
||
es die [[Delaunay-Triangulation]], welche |
es die [[Delaunay-Triangulation]], welche besonders spitze Dreiecke vermeidet, oder die [[Minimum-Weight-Triangulation]], |
||
welche die Gesamtlänge aller Kanten minimiert. |
welche die Gesamtlänge aller Kanten minimiert. |
||
== Siehe auch == |
== Siehe auch == |
||
Version vom 20. Mai 2006, 00:03 Uhr
--Eva K. Post 23:51, 19. Mai 2006 (CEST)
Eine Triangulation einer Menge von Punkten P in der Ebene ist ein ebener Dreiecksgraph, dessen Knoten genau die Punkte aus P sind. Alle inneren Gebiete einer Triangulierung sind Dreiecke, während das äußere Gebiet von der konvexen Hülle von P begrenzt wird.
Ist die Menge P in konvexer Lage, so ist die Anzahl der möglichen Triangulationen genau die n-2-te Catalan-Zahl, wobei n die Kardinalität von P bezeichnet.
Oft ist man daran interessiert, eine Triangulation mit besonderen Eigenschaften zu berechnen. Zum Beispiel gibt es die Delaunay-Triangulation, welche besonders spitze Dreiecke vermeidet, oder die Minimum-Weight-Triangulation, welche die Gesamtlänge aller Kanten minimiert.