2
$\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 
  • 1
    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 http://en.wikipedia.org/wiki/Gauss_circle_problem2011-06-03

4 Answers 4

-1

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.

  • 0
    @Zev Well dang.2011-06-04
2

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.

  • 1
    @NelsonLaQuet, finding a formula is a nice exercise. Note that the square number appear diagonally down to right. $I$f you $s$till need help, please ask.2011-06-03
2

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

  • 0
    After some testing, this is indeed what I was looking for. Thanks!2011-06-03
1

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.