3
$\begingroup$

Is there any way that I can mathematically determine a unique index number for 2D points that increases the further away I get from the origin? I do not know how far out that this coordinate system extends to.

I am working on a system where I need random access to data indexed by a 2D point.

In other words, I need a function that will always return a unique integer given the same two integers, but not conflict with other sets of numbers. Think of it like a hash. However, I need the indices generated to increase as the distance from the origin increases - this is so that my index growth remains constant as I add more data.

EDIT:

Here is some procedurally generated data that would work as a solution. I simply need a function that I can execute in constant time that produces something to the effect of:

   0,   0 = 0
  -1,   0 = 1
   0,  -1 = 2
   0,   1 = 3
   1,   0 = 4
  -1,  -1 = 5
  -1,   1 = 6
   1,  -1 = 7
   1,   1 = 8
  -2,   0 = 9
   0,  -2 = 10
   0,   2 = 11
   2,   0 = 12
  -2,  -1 = 13
  -2,   1 = 14
  -1,  -2 = 15
  -1,   2 = 16
   1,  -2 = 17
   1,   2 = 18
   2,  -1 = 19
   2,   1 = 20
  -2,  -2 = 21
  -2,   2 = 22
   2,  -2 = 23
   2,   2 = 24
  -3,   0 = 25
   0,  -3 = 26
  -3,  -1 = 27
  -3,   1 = 28
  -1,  -3 = 29
   1,  -3 = 30
  -3,  -2 = 31
  -3,   2 = 32
  -2,  -3 = 33
   2,  -3 = 34
  -3,  -3 = 35
$\endgroup$
1
  • 1
    $\begingroup$ Two answers are posted, both generally increasing with distance from the origin, but neither monotonic. Is that a requirement? It makes the problem much harder. You would need a solution to the Gauss circle problem: see en.wikipedia.org/wiki/Gauss_circle_problem $\endgroup$
    – Ross Millikan
    Jun 3, 2011 at 5:10

4 Answers 4

Reset to default
3
$\begingroup$

First suppose the coordinates are non-negative. You can define $$f(x,y) = \binom{x+y+1}{2} + x.$$ Here $\binom{z}{2} = z(z-1)/2$.

In order to handle arbitrary integers, define $$g(x) = \begin{cases} 0 & x = 0, \\ 2x - 1 & x > 0, \\ -2x & x < 0. \end{cases}$$ Then the function you want is $$h(x,y) = f(g(x),g(y)).$$

$\endgroup$
2
  • $\begingroup$ I implemented this and it seems very promising. I'm going to be doing some more testing tomorrow on this, but I am pretty sure this is what I need. I would upvote you if I could... Thanks! $\endgroup$
    – user11686
    Jun 3, 2011 at 6:05
  • $\begingroup$ After some testing, this is indeed what I was looking for. Thanks! $\endgroup$
    – user11686
    Jun 3, 2011 at 21:14
2
$\begingroup$

If you're using points with integer coordinates, then try a spiral like this one: http://upload.wikimedia.org/wikipedia/commons/1/1d/Ulam_spiral_howto_all_numbers.svg.

$\endgroup$
2
  • $\begingroup$ This is very very close to what I am looking for. However, I need a function that I can use to calculate one of those values given a point - in constant time. $\endgroup$
    – user11686
    Jun 3, 2011 at 5:17
  • 1
    $\begingroup$ @NelsonLaQuet, finding a formula is a nice exercise. Note that the square number appear diagonally down to right. If you still need help, please ask. $\endgroup$
    – lhf
    Jun 3, 2011 at 12:55
2
$\begingroup$

It is believed (but not proved) that $f(x,y)=x^5+y^5$ never takes on the same value twice except, of course, for $f(x,y)=f(y,x)$. It certainly never takes on the same value twice for as far as anyone has been able to compute - call it "an industrial grade theorem." Like the other suggestions, it increases, but not monotonely, with increasing distance from the origin.

$\endgroup$
-1
$\begingroup$

If the coordinates of the points can have any real value, then I don't think such a function is possible because you are looking for an injective function from $\mathbb{R}^2$ to $\mathbb{R}$.

EDIT: The examples came up after I posted this. If you're just using integers, then such a function is possible.

$\endgroup$
2
  • $\begingroup$ $\mathbb{R}^2$ and $\mathbb{R}$ have the same cardinality, and therefore are in bijection. See here. $\endgroup$
    – Zev Chonoles
    Jun 3, 2011 at 6:17
  • $\begingroup$ @Zev Well dang. $\endgroup$
    – Tauf
    Jun 4, 2011 at 5:01

Your Answer

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