Divide-and-Conquer-Algorithmus:

Dieser Algorithmus funktioniert ähnlich wie der Recursive-Split-Algorithmus und besteht aus den folgenden Schritten:

Schritt 1:

Die Geometrie wird rekursiv zerteilt, bis jede Teilgeometrie nur noch vier Punkte enthält.

Schritt 2:

Aus dem Viereck werden durch Teilen entlang der kürzeren Diagonalen zwei Dreiecke erzeugt.

Schritt 3:

Beim Zusammenfügen der Teilgeometrien werden durch Außenkanten der Teilgeometrien benachbarte Dreiecke als Viereck betrachtet und entlang der kürzeren Kante in zwei Dreiecke geteilt.

Die Laufzeit dieses Algorithmus verhält sich mit ${\cal O}(n \log n)$ und ist damit der schnellste hier beschriebene Algorithmus. Eine Parallelisierung des Algorithmus zur Nutzung auf Parallelrechnern ist aufgrund der Bisektion denkbar.