Binary space-partitioning trees

Theory

Nodes

A node is a closed subset of $RR^n$ . Denote the set of all nodes by $C = {S sub RR^n : S text( is a node)}$ and let $S = {S_1, ..., S_m} sub C$ . A node $B in S$ is called a descendant of a node $A in S$ if $B sub A$ and $B != A$ . If $B$ is a descendant of $A$ , then $A$ is called an ascendant of $B$ . A node $A_c in S$ is called a child of a node $A in S$ if $A_c$ is a descendant of $A$ and there is no descendant $B in S$ of $A$ which would also be an ascendant of $A_c$ . If $A_c$ is a child of $A$ , then $A$ is called a parent of $A_c$ .

BSP-tree

A binary space-partitioning tree or a bsp-tree, is a directed graph $T = (B, D)$ , such that

$B = {B_1, ..., B_m} sub C$ .
$D = {(B_i, B_j) in B^2 : B_i text( is a child of ) B_j}$ .
$\forall i, j: \exists k: B_i sub B_k and B_j sub B_k$
$\forall i: B_i$ either has no children or it has exactly two children $B_{l(i)}$ and $B_{r(i)}$ such that $B_{l(i)} uu B_{r(i)} = B_i$ and $I(B_{l(i)}) nn I(B_{r(i)}) = \emptyset$ , where $I$ refers to the interior of a point-set.

These definitions imply that $T$ is a binary tree, explaining the name. A node which has no children is called a leaf node, while the unique node which has no parent is called the root node. A node which is not a leaf node is called a split node. Two nodes which have the same parent are called siblings.

Point BSP-tree

A point BSP-tree is a pair $(T, P)$ such that

$T = (B, D)$ is a BSP-tree, where $B = {B_1, ..., B_m}$ .
$P = {P_1, ..., P_m}$ , where $P_i sub RR^n$ are finite sets.
$\forall i: P_i sub B_i$ .
$\forall i: B_i$ is not a leaf node $=> P_i = P_{l(i)} uu P_{r(i)}$ .

Kd-tree

A kd-tree is a BSP-tree with the restriction that the set of all nodes is restricted to closed axis-aligned boxes. Let a split-node $B$ in a kd-tree have children $B_l$ and $B_r$ . Then there is a unique axis-aligned plane which passes through the points in $B_l nn B_r$ , called the splitting plane of $B$ . The index of the standard basis axis which corresponds to the normal of this plane is called the splitting axis.

Point kd-tree

A point kd-tree is a point bsp-tree which is also a kd-tree.

Practice

A BSP-tree makes it possible to design efficient algorithms for several geometric problems. Such problems include ray casting, nearest neighbor searching, and range searching. The efficiency of these algorithms rely on the ability to skip exploring a large part of the space if that is known not to affect the result. The BSP-tree is effectively a multi-dimensional generalization of the binary tree. In practice, kd-trees offer the best properties of the BSP-trees, from many point of views.

Kd-tree vs BSP-tree

Restricting the splitting planes to be orthogonal with the standard basis axes has a number of advantages. Some of these are:

A plane can be described by a single integer (the splitting axis), and a real number (distance of the plane from the origin). In contrast, arbitrary planes require $O(n)$ storage in $RR^n$ .
It can be tested with a single comparison on which side of the splitting plane a point is. Because there is no arithmetic involved, there are no numerical problems with rounding: the result is exact. In contrast, arbitrary planes require $O(n)$ time in $RR^n$ , and the result might be wrong due numerical problems.
There are splitting rules which are easy to compute and result in excellent performance for nearest neighbor searching and ray casting. In contrast, with arbitrary planes, to the best of our knowledge, there is currently no known splitting rules that would have both of these properties.
When doing nearest neighbor searching, there is a technique to incrementally compute the exact distance from the search point to the nearest node. This allows for more efficient culling of space which in turn increases performance. In contrast, this is very hard to achieve with arbitrary splitting planes because the complexities of the nodes are not bounded.