next up previous contents
Nächste Seite: Rupperts Algorithmus: Aufwärts: Einfügen von Punkten Vorherige Seite: Einfügen von Punkten   Inhalt


Chew's erster Algorithmus:
[Chew 1989] schlägt einen Algorithmus zum Einfügen von Punkten vor. Als obere Grenze für die Qualität von Dreiecken verwendet er das Umkreisradius-Kriterium (siehe Abschnitt 3.4.2.1) und setzt ${\cal B}=1$ als Maximalwert an. Chew teilt alle Dreiecke auf, deren Umkreisradius größer als die kürzeste Kante im Netzwerk ($h_{min}$) ist. Hierdurch wird erreicht, dass die maximale Kantenlänge im gesamten Netz $2 \cdot h_{min}$ nicht übersteigt.