sorting - Heuristics to sort array of 2D/3D points according their mutual distance

Question

Consider array of points in 2D,3D,(4D...) space ( e.g. nodes of unstructured mesh ). Initially the index of a point in array is not related to its position in space. In simple case, assume I already know some nearest neighbor connectivity graph.

I would like some heuristics which increase probability that two points which are close to each other in space would have similar index (would be close in array).

I understand that exact solution is very hard (perhaps similar to Travelling salesman problem ) but I don't need exact solution, just something which increase probability.

My ideas on solution:

some naive solution would be like:

1. for each point "i" compute fitness E_i given by sum of distances in array (i.e. index-wise) from its spatial neighbors (i.e. space-wise)
   E_i = -Sum_k ( abs( index(i)-index(k) ) ) 
   where "k" are spatial nearest neighbors of "i" 
2. for pairs of points (i,j) which have low fitness (E_i,E_j) 
   try to swap them, 
   if fitness improves, accept

but the detailed implementation and its performance optimization is not so clear.

Other solution which does not need precomputed nearest-neighbors would be based on some Locality-sensitive_hashing

I think this could be quite common problem, and there may exist good solutions, I do not want to reinvent the wheel.

Application:

• improve cache locality, considering that memory access is often bottleneck of graph-traversal
• it could accelerate interpolation of unstructured grid, more specifically search for nodes which are near the smaple (e.g. centers of Radial-basis function).

Answer 1

The problem you are trying to solve has meaning iff, given a point p and its NN q, then it is true that the NN of q is p.

That is not trivial, since for example the two points can represent positions in a landscape, so the one point can be high in a mountain, so going from the bottom up to mountain costs more that the other way around (from the mountain to the bottom). So, make sure you check that's not your case.

---

Since TilmannZ already proposed a solution, I would like to emphasize on LSH you mentioned. I would not choose that, since your points lie in a really low dimensional space, it's not even 100, so why using LSH?

I would go for CGAL's algorithm on that case, such as 2D NNS, or even a simple kd-tree. And if speed is critical, but space is not, then why not going for a quadtree (octree in 3D)? I had built one, it won't go beyond 10 dimensions in an 8GB RAM.

If however, you feel that your data may belong in a higher dimensional space in the future, then I would suggest using:

1. LSH from Andoni, really cool guy.
2. FLANN, which offers another approach.
3. kd-GeRaF, which is developed by me.