<p>This is impossible in general.</p>

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

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

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

CC BY-SA 3.0
2014-09-18T13:24:34.127Z
2014-09-18T13:24:34.127Z
R B
<p>I was wondering if there is any algorithm, theoretical or already implemented, or if its even possible at all, where, given <code>N</code> random <code>points (x,y)</code> 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.</p>

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

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

<p>Thanks in advance!</p>

CC BY-SA 3.0
2014-09-18T13:14:19.527Z
seems impossible
Denis
<graph-theory><application-of-theory><applicative>
How to map random cardesian points in a 2d array
BugShotGG
# How to map random cardesian points in a 2d array

(Asked by: username_0 on 2014-09-18)

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!

**Tags:** graph-theory, application-of-theory, applicative
> **Comments:**
> **username_1**: seems impossible  

---

## 1 answers

### Answer by username_2 on 2014-09-18. Score: 1

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.


---

