When it comes to finding approximate neighbors, there is a nice simple trick to help address the curse of dimensionality. An easy algorithm to find nearby neig

When it comes to finding approximate neighbors, there is a nice simple trick to help address the curse of dimensionality. An easy algorithm to find nearby neighbors is to split space into the generalization of squares / cubes, aka hypercubes. Then look at all the surrounding cubes and compile a list of all the neighbors in them. You can do this with a precomputed hash table mapping cubes to lists of points in that cube. This suffers the curse because a cube in n dimensions has 3^n - 1 neighbors (it is in the middle of a 3x3x..x3 hypercube). Make it a little better with hash table from every cube corner to a list of points in all surrounding cubes, a benefit of 3^n down to 2^n lookups -- still exponential. Simple idea: Split up space using triangles instead of squares (aka simplices instead of hypercubes). We just went from 2^n lookups down to n+1 (one for each corner) -- pretty good. The questions are then: (1) how do you tile n-space with n-dim'l triangles/pyramids (simplices), and (2) how do we get highly regular simplices to do that? [Regularity is good because you usually want a sphere-like radius-based lookup.] It turns out there's a vertex-transitive simplex that tiles any dimension, and as a bonus is easy to work with computationally. ("Vertex-transitive" is a type of regularity where basically every vertex "looks the same" as every other.) So if you care about point neighbors within a certain approximate radius, these tricks are extremely helpful. Reference: http://www.siam.org/proceedings/soda/2010/SODA10_094_neylont.pdf http://www.siam.org/proceedings/soda/2010/SODA10_094_neylont...