Baryzentrische Unterteilung - Barycentric subdivision

In der Geometrie ist die baryzentrische Unterteilung eine Standardmethode zum Teilen eines beliebigen konvexen Polygons in Dreiecke , eines konvexen Polyeders in Tetraeder oder im Allgemeinen eines konvexen Polytops in Vereinfachungen mit derselben Dimension , indem die Barycenter ihrer Flächen in einer bestimmten verbunden werden Weg.

Der Name wird auch in der Topologie für eine ähnliche Operation an Zellkomplexen verwendet . Das Ergebnis ist topologisch äquivalent zu dem der geometrischen Operation, aber die Teile haben eine beliebige Form und Größe. Dies ist ein Beispiel für eine endliche Unterteilungsregel .

Beide Operationen haben eine Reihe von Anwendungen in der Mathematik und in der geometrischen Modellierung , insbesondere wenn eine Funktion oder Form stückweise angenähert werden muss , z . B. durch einen Spline .

Baryzentrische Unterteilung eines Simplex

Baryzentrische Unterteilung des 2-Simplex oder Dreiecks

Die baryzentrische Unterteilung (fortan BCS ) eines eindimensionalen Simplex besteht aus ( n  + 1)! -dimensionale Vereinfachungen. Jedes Stück mit Scheitelpunkten kann einer Permutation der Scheitelpunkte von zugeordnet werden , so dass jeder Scheitelpunkt das Schwerpunktzentrum der Punkte ist . ${\ displaystyle n}$ ${\ displaystyle S}$ ${\ displaystyle n}$${\ displaystyle v_ {0}, v_ {1}, \ dots, v_ {n}}$ ${\ displaystyle p_ {0}, p_ {1}, \ dots, p_ {n}}$${\ displaystyle S}$${\ displaystyle v_ {i}}$${\ displaystyle p_ {0}, p_ {1}, \ dots, p_ {i}}$

4 Stufen der baryzentrischen Unterteilung

Insbesondere besteht das BCS eines einzelnen Punktes (eines 0-dimensionalen Simplex) aus diesem Punkt selbst. Das BCS eines Liniensegments (1-Simplex) besteht aus zwei kleineren Segmenten, die jeweils einen Endpunkt (0-dimensionale Fläche) mit dem Mittelpunkt ihrer selbst (1-dimensionale Fläche) verbinden. ${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$

Das BCS eines Dreiecks teilt es in sechs Dreiecke; Jeder Teil hat einen Scheitelpunkt im Schwerpunkt , einen anderen in der Mitte einer Seite und den letzten an einem der ursprünglichen Scheitelpunkte. ${\ displaystyle S}$${\ displaystyle v_ {2}}$${\ displaystyle S}$${\ displaystyle v_ {1}}$${\ displaystyle v_ {0}}$

Das BCS eines Tetraeders unterteilt es in 24 Tetraeder; Jeder Teil hat einen Scheitelpunkt in der Mitte von , einen auf einer Fläche, einen entlang einer Kante und den letzten an einem Scheitelpunkt von . ${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$

Ein wichtiges Merkmal von BCS ist die Tatsache, dass der maximale Durchmesser eines eindimensionalen Simplex zumindest um den Faktor schrumpft . ${\ displaystyle n}$${\ displaystyle {\ frac {n} {n + 1}}}$

Baryzentrische Unterteilung eines konvexen Polytops

Eine weitere Möglichkeit , die BCS eines simplex definieren ist , jeden Teil an eine Sequenz zu assoziieren von Gesichtern von mit zunehmenden Dimensionen, so dass eine Facette von , für von 0 bis . Dann ist jeder Scheitelpunkt des entsprechenden Stücks der Schwerpunkt des Gesichts . ${\ displaystyle S}$${\ displaystyle F_ {0}, F_ {1}, \ dots, F_ {n}}$${\ displaystyle S}$${\ displaystyle F_ {i}}$${\ displaystyle F_ {i + 1}}$${\ displaystyle i}$${\ displaystyle n-1}$${\ displaystyle v_ {i}}$${\ displaystyle F_ {i}}$

Diese alternative Definition kann auf das BCS eines beliebig- dimensionalen konvexen Polytops in eine Reihe von Vereinfachungen erweitert werden. So hat das BCS eines Fünfecks zum Beispiel 10 Dreiecke: Jedes Dreieck ist drei Elementen von - bzw. einer Ecke , einer Seite, die auf diese Ecke fällt, und sich selbst zugeordnet. ${\ displaystyle n}$${\ displaystyle n}$ ${\ displaystyle P}$${\ displaystyle F_ {0}, F_ {1}, F_ {2}}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$

In ähnlicher Weise besteht das BCS eines Würfels aus 48 Tetraedern, von denen jedes einer Folge verschachtelter Elemente zugeordnet ist - einem Scheitelpunkt, einer Kante, einer Fläche und dem gesamten Würfel. Beachten Sie, dass es 8 Auswahlmöglichkeiten für , 3 für (gegeben ) und 2 für (gegeben ) gibt. ${\ displaystyle F_ {0}, F_ {1}, F_ {2}, F_ {3}}$${\ displaystyle F_ {0}}$${\ displaystyle F_ {1}}$${\ displaystyle F_ {0}}$${\ displaystyle F_ {2}}$${\ displaystyle F_ {0}, F_ {1}}$

Baryzentrische Unterteilung in der Topologie

Die baryzentrische Unterteilung ist ein wichtiges Werkzeug in der Theorie der einfachen Homologie , wo sie verwendet wird, um feinere einfache Komplexe zu erhalten (die die ursprünglichen enthalten, dh mit einfacheren). Dies ist wiederum entscheidend für den Satz der einfachen Annäherung , der grob besagt, dass man jede kontinuierliche Funktion zwischen Polyedern durch eine (endliche) einfache Karte approximieren kann , wenn die jeweiligen von ihnen realisierten einfachen Komplexe ausreichend unterteilt sind. Letztendlich ist diese Approximationstechnik ein Standardbestandteil für den Beweis, dass einfache Homologiegruppen topologische Invarianten sind.

Eine Verallgemeinerung der baryzentrischen Unterteilung kann auch für einen Zellkomplex definiert werden . Informell kann ein solches Objekt als eine Ansammlung von einem oder mehreren Gummistücken ( Zellen ) betrachtet werden, die jeweils wie ein konvexes Polytop geformt sind und durch ihre Facetten aneinander geklebt werden - möglicherweise mit viel Dehnung und Verdrehung.

Die topologische Version von BCS ersetzt jede Zelle durch eine Zusammenstellung von Gummi-Simplices, die ebenfalls durch ihre Facetten zusammengeklebt und möglicherweise deformiert sind. Das Verfahren besteht darin, (1) für jede Zelle eine Verformungskarte auszuwählen , die sie in ein geometrisches konvexes Polytop umwandelt, wobei ihr Einfall und ihre topologischen Verbindungen erhalten bleiben; (2) das geometrische BCS an diesem Polytop durchführen; und dann (3) ordne die resultierende Unterteilung wieder den ursprünglichen Zellen zu.

Das Ergebnis einer baryzentrischen Unterteilung, wenn es als abstrakter einfacher Komplex betrachtet wird , ist ein Beispiel für einen Flaggenkomplex . Es hat einen Scheitelpunkt für jede Zelle des ursprünglichen Zellkomplexes und eine maximal dimensionale Zelle für jede Flagge (eine Sammlung von Zellen unterschiedlicher Dimensionen, die alle durch Einschluss miteinander verbunden sind) des ursprünglichen Zellkomplexes.

Anwendungen

Die baryzentrische Unterteilung wird hauptsächlich verwendet, um ein beliebig kompliziertes konvexes Polytop oder einen topologischen Zellkomplex durch eine Zusammenstellung von Stücken zu ersetzen, die alle von begrenzter Komplexität sind ( tatsächlich Vereinfachungen ). Eine typische Anwendung ist die Modellierung der Form eines Autokörpers durch eine Spline - eine abschnittsweise definierte Polynom - Funktion . Die Algebra solcher Funktionen wird viel einfacher und einfacher zu programmieren, wenn jedes "Stück" ein "topologisches Dreieck" ist, dh genau drei anderen Stücken zugeordnet ist. Für einen menschlichen Benutzer ist es jedoch möglicherweise natürlicher, die Form zu entwerfen, indem Patches mit liberaleren Formen und Topologien verbunden werden. Die baryzentrische Unterteilung ist eine bequeme Möglichkeit, dieses "benutzerfreundliche" Modell in ein "computerfreundliches" Modell umzuwandeln.

Wiederholte baryzentrische Unterteilung

Bei der Approximation einer mathematischen Funktion oder einer Oberfläche durch einen Spline wird die Genauigkeit der Approximation normalerweise durch die Stückgröße bestimmt - je größer die Stücke, desto größer der Fehler. Daher ist es oft notwendig, große Stücke in kleinere zu teilen, um eine vorgeschriebene Genauigkeit zu erreichen.

Theoretisch könnte BCS für diesen Zweck verwendet werden, da es die Eigenschaft hat, dass die längste Kante eines Stücks um einen Faktor kleiner als die längste Kante des ursprünglichen Polytops ist . Daher kann durch ausreichend häufiges Anwenden von BCS die größte Kante so klein wie gewünscht gemacht werden. ${\ displaystyle n / (n + 1)}$

In der Praxis ist BCS für diesen Zweck jedoch nicht gut geeignet. Zum einen multipliziert jede Anwendung nach der ersten die Anzahl der Vereinfachungen mit . BCS multipliziert auch den Grad jedes ursprünglichen Scheitelpunkts mit und den Grad jeder Kante mit . Darüber hinaus wird das BCS alle Vereinfachungen aufteilen, auch diejenigen, die bereits klein genug sind. Schließlich macht jede BCS-Stufe die Vereinfachungen nicht nur kleiner, sondern auch "dünner", dh sie erhöht tendenziell ihr Seitenverhältnis (das Verhältnis zwischen der längsten und der kürzesten Kante). Aus all diesen Gründen wendet man in der Praxis selten mehr als eine Runde BCS an, und stattdessen werden andere Unterteilungsschemata verwendet. ${\ displaystyle (n + 1)!}$${\ displaystyle n!}$${\ displaystyle (n-1)!}$

Relative baryzentrische Unterteilung

Für einfache Komplexe definiert man die relative baryzentrische Unterteilung von Modulo , die aus solchen Simplexen mit Eckpunkten besteht , die einer Folge von richtigen Flächen und Barycentern von Simplexen in zugeordnet sind . ${\ displaystyle L \ subset K}$${\ displaystyle K ^ {*}}$${\ displaystyle K}$ ${\ displaystyle L}$${\ displaystyle v_ {0} \ dots v_ {k} B (S '_ {1}) \ dots B (S' _ {l})}$${\ displaystyle S_ {0} <\ cdots <S_ {k}}$${\ displaystyle L}$${\ displaystyle B (S '_ {i})}$${\ displaystyle K \ setminus L}$

Klar bleibt ein Subkomplex von . Nur die Simplexe schrumpfen weg . ${\ displaystyle L}$${\ displaystyle K ^ {*}}$${\ displaystyle L}$

Verwandte Begriffe

Falsche baryzentrische Unterteilung

Manchmal wird der Begriff "baryzentrische Unterteilung" zu Unrecht für jede Unterteilung eines Polytops in Vereinfachungen verwendet, die einen Scheitelpunkt am Schwerpunkt und die entgegengesetzte Facette an der Grenze von haben . Während diese Eigenschaft für die wahre baryzentrische Unterteilung gilt, gilt sie auch für andere Unterteilungen, die nicht das BCS sind. ${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$

Wenn man zum Beispiel einen geraden Schnitt vom Schwerpunkt eines Dreiecks zu jeder seiner drei Ecken macht, erhält man eine Unterteilung in drei Dreiecke. Wenn man diese Idee verallgemeinert, erhält man ein Schema zur Unterteilung eines eindimensionalen Simplex in Vereinfachungen. Diese Unterteilung ist jedoch nicht das BCS. ${\ displaystyle n}$${\ displaystyle n + 1}$

Einfache Sets

Die baryzentrische Unterteilung kann auch für einfache Mengen in einer Weise definiert werden, die (in Bezug auf den topologischen Realisierungsfunktor) mit der obigen Unterteilung von Vereinfachungen kompatibel ist.

Graphentheorie

Der Begriff baryzentrische Division wird auch in der Graphentheorie verwendet ( Barycentric_Subdivision (Graphentheorie) ).

Anmerkungen

Siehe auch

• Apollonian Netzwerk
• Zellkomplex
• Finite-Elemente-Methode
• Netzgenerierung
• Polytop
• Spline