# How to map random cardesian points in a 2d array

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...

• seems impossible – 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.