Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
share|improve this question
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 en.wikipedia.org/wiki/Gauss_circle_problem –  Ross Millikan Jun 3 '11 at 5:10

4 Answers 4

up vote 2 down vote accepted

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

share|improve this answer
    
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! –  NelsonLaQuet Jun 3 '11 at 6:05
    
After some testing, this is indeed what I was looking for. Thanks! –  NelsonLaQuet Jun 3 '11 at 21:14

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.

share|improve this answer
    
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. –  NelsonLaQuet Jun 3 '11 at 5:17
    
@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. –  lhf Jun 3 '11 at 12:55

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.

share|improve this answer

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.

share|improve this answer
    
$\mathbb{R}^2$ and $\mathbb{R}$ have the same cardinality, and therefore are in bijection. See here. –  Zev Chonoles Jun 3 '11 at 6:17
    
@Zev Well dang. –  Tauf Jun 4 '11 at 5:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.