Performanz des Octalbaumes.

Der Octalbaum lässt sich wie beschrieben in $\O(n)$ aufbauen. In jeder Rekursionsstufe müssen alle Punkte betrachtet werden. Da aber nur wenige Iterationen benötigt werden (vgl. Abbildung 5.4), sind die Konstanten im Algorithmus klein und das Verfahren läuft im Bruchteil einer Sekunde (PIII-600) ab.

Die Anzahl der Quader steigt nur langsam. Daher ist der Speicherverbrauch des Octalbaumes hauptsächlich durch die Anzahl der im Baum gespeicherten Daten bestimmt, also $\O(n)$. Sie ist gleichzeitig die Obergrenze für die Anzahl der Blätter im Baum. Abbildung 5.5 zeigt die Zahl der Quader im Octalbaum verglichen mit der maximal möglichen, also jener eines vollständigen Octalbaums.

Abbildung: Anzahl der Blätter im Octalbaum (logarithmisch aufgetragen).