Image:David M. Mount and Sunil Arya;





Images from simplistic implementation of the Octree algorithm in Maya. Primarily as an exercise to understand its API and class derivation within it.

BSP
"Binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree."

Wikipedia Accessed Aug 2007

Octree
"An octree is a tree data structure in which each internal node has up to eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants."

wikipedia Accessed Aug 2007

Approximate Nearest Neighbour
"Computing exact nearest neighbors in dimensions much higher than 8 seems to be a very difficult task. Few methods seem to be significantly better than a brute-force computation of all distances. However, it has been shown that by computing nearest neighbors approximately, it is possible to achieve significantly faster running times (on the order of 10's to 100's) often with a relatively small actual errors. ...."

David M. Mount and Sunil Arya

Even accounting for the amateur nature of our attempt, it would appear that the above holds true in 3 dimensions as well ie. an octree algorithm provides a significant advantage over brute calculation of distances only when the point distribution is sparse, point sets are large (above 50000) and some tolerances are allowed in terms of measurement.