I was wondering if there is any algorithm, theoretical or already implemented, or if its even possible at all, where, given N random points (x,y) we can relatively map them in a 2d array where each mapped point in the 2d-array has the property that its neighboring points (at most 8 points around it) are the closest to that point.

I would also like to add an extra restriction that no node in the 2d array is NULL meaning that if we have for example N = 1 Million elements then the 2d array would be sqrt(N) x sqrt(N) or 1000 x 1000 dimension, where each element of that array occupies a point.

In addition, we can also consider sorting, if it can help, as of x-coordinate and as of y-coordinate...

Thanks in advance!

  • $\begingroup$ seems impossible $\endgroup$ – Denis Sep 18 '14 at 13:14

This is impossible in general.

The reason is that the grid-distance is symmetric while being closest neighbors is not a symmetric relation.

If you have many points ($\geq 9$) close to the origin and then a point at, say, $(M,0)$ for some large $M$.

The point at $(M,0)$ has a its closest neighbors as some of the points which are closest to the origin, but these points consider it as the farthest point from them.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.