Create a neighbourhood graph from a list of voxels faster than in O(n^2)?

Question

I'm currently creating a "neighbourhood graph" by doing roughly this:

for every voxel
  look at every other unseen voxel 
    check if neighbours

which runs roughly in n squared (minus n). It is acceptable for a certain number of voxels, but obviously it takes much more time with bigger lists.

Another naive solution is simply to put everything into either a big 3d array, or in a hashmap, which would run in O(n) but at the expense of much more memory.

Is there a faster way? I can't seem to enter the right search terms in google...

Answer 1

You might want to look at space partitioning trees like the octree or k-d tree structures. These structures usually can be built very efficiently (O(n) or O(n log n), IIRC), and then provide extremely fast lookups for finding either nearest neighbors or points within a given bounding box. Using one of these structures should give you a huge performance boost without the huge memory cost of making a giant 3D array.

Hope this helps!