Aufbau des 3D-Baumes.

Gegeben sei eine Menge $P$ von 3D-Datenpunkten. Die erste Aufgabe besteht darin, den 3D-Baum zu konstruieren. Dabei soll $P$ in zwei ungefähr gleich große Regionen aufgespalten werden. Als Separierung dient eine Ebene, die parallel zu der $(x,y,0)$, $(0,y,z)$ oder $(x,0,z)$-Ebene verläuft und die durch den Datenmittelpunkt geht. Datenpunkte links neben der Ebene werden im linken Teilbaum gespeichert, während Punkte rechts neben der Ebene im zweiten Teilbaum abgelegt werden. Da etwa gleich große Bereiche entstehen sollen, alterniert in der Regel die Lage der Ebene. In Anhang B.1.1 befindet sich der oben beschriebene Algorithmus im gekürzten Quellcode.

Das Verfahren teilt nicht in jedem Fall die Daten auf zwei gleich große Teilbäume auf. Dazu müsste man nicht den Datenmittelpunkt, sondern den Punkt finden, der bei gegebener Trennebene die Daten gleichmäßig zur Verteilung bringt. Ein solch zeitaufwendiger Rechenschritt wird nicht durchgeführt.