You can also download the PDF version (1.0 MB).
An appendix describes more mathematical
details.
The approach attains its speed by a hierarchical data structure, the BoxTree, and an associated divide-and-conquer traversal algorithm, which exploits the very special geometry of boxes. Boxes were chosen, because they offer much tighter space partitioning than spheres.
The method is generic, so it can be endowed with other semantics operating on polyhedra.
The algorithm is fairly simple to implement
and it is described in great detail in an
appendix to facilitate easy implementation.
The construction of the data structure is very simple and very fast.
Timing results show the efficiency of this approach.