next up previous contents
Next: 7.2.5 Implementierung der Vergröberung Up: 7.2 Lokale Verfeinerung und Previous: 7.2.3 Ermittlung der Anpassungszerlegung

7.2.4 Effizienzbetrachtungen

Die Rekursionstiefe des beschriebenen Algorithmus ist nun stark von der Art der Elemente und deren verschiedenen Zerlegungsarten abhängig. Betrachtet man vorerst einen Satz von Elementen und Zerlegungen, bei dem für jede mögliche Punktkonstellation eine Zerlegungsvariante existiert, dann ist die maximal auftretende Rekursionstiefe gleich der Anzahl der Hierarchieebenen im Gitter, da mit jeder Rekursion genau eine Hierarchiestufe abgedeckt werden kann. Fehlt nun eine Zerlegungsart, so muß zumindest eine Rekursion mehr ausgeführt werden, da nun aufgrund der topologischen Verfeinerung weitere Punkte notwendig sind, die bei -- jetzt bereits indirekten -- Nachbarn eingetragen werden müssen. Die Rekursion bricht also erst dann ab, wenn in einem Nachbarn kein zusätzlicher Punkt aufgrund einer fehlenden Zerlegung eingefügt werden muß. Abb. 7.12 zeigt eine derartige Situation. Die grau hinterlegten Dreiecke in Abb. 7.12a entsprechen der Zerlegung gleichseitiger Dreiecke mittels jeweils einem zusätzlichen Punkt. Das dunkelgraue Dreieck soll nun vollständig verfeinert werden (Abb. 7.12b). Zur weiteren Anpassung muß nun das angrenzende Dreieck um einen Punkt erweitert werden. Nachdem jedoch keine Zerlegung mit zwei Punkten existiert, kann nur die vollständige Verfeinerung durchgeführt werden (Abb. 7.12c). Für den Nachbarn dieses Elementes gilt aber wieder dasselbe, sodaß die Rekursion erst abbricht, wenn aufgrund der topologischen Abhängigkeit kein weiterer Punkt eingefügt werden muß (Abb. 7.12d).


  
Abbildung 7.12: Ablauf der Rekursion bei topologischer Verfeinerung.
\begin{figure}
 \centerline{\resizebox {0.9\textwidth}{!}{\includegraphics{recursion_tri.eps}}
}\end{figure}

Die Rekursionstiefe kann also mitunter recht groß werden, ist jedoch immer auf die Anzahl der Übergangselemente im Gitter beschränkt. Bei praktischen Beispielen ist dies in der Regel nur ein geringer Anteil der gesamten Elemente im Gitter. Der gesamte Aufwand zur Adaptierung eines Gitters ist in etwa proportional zu der Anzahl der verfeinerten Elemente, denn trotz der Rekursionen wird ein Element nur so oft behandelt, als darin Punkte eingefügt werden müssen.


next up previous contents
Next: 7.2.5 Implementierung der Vergröberung Up: 7.2 Lokale Verfeinerung und Previous: 7.2.3 Ermittlung der Anpassungszerlegung
Ernst Leitner
1997-12-30