How can I index 2 dimensional points, starting at the origin and going outwards?

Question

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

Answer 1

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

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

Answer 3

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.

Answer 4

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.