# In an N-dimensional space filled with points, systematically find the closest point to a specified point

This is my first post on the mathematics stack exchange site. If I am posting this question on the wrong site, I apologize and please let me know so I can delete it.

I am a programmer, and one thing we have to worry about is optimization. This is why my question probably isn't as simple as it seems: given a point (i.e point A) in an N-dimensional space, find the closest point to that point (i. e. in a set of points B-Z in 5-dimensions).

Now the obvious solution is to find the euclidean distance from the given point to every other point and take the minimum, but this can be extremely inefficient if I am working with a large set of points (I am talking maybe a billion or so). Memory should not be a problem, I am just worried about speed.

One untested, simple idea I had on this was to create an N amount of lists. The Nth list will be sorted by the nth dimension. I can then take my given point of 5-dimension, lets make it (3, 9, 1, 0, 2). I will go through each sorted array, starting at where x1 = 3 in the first array, and then where x2 = 9 in the second array, etc. and spread out until a certain predetermined point so that I won't have to go through all of the points.

I am not to sure if that method made sense, but even if it didn't, is there another way of going about this?

Thank you!

-
Grr. I wasn't too sure exactly what to search for to get an article like that, but that actually addresses exactly what I was looking for. If any one has any solution from there, or any other solution otherwise, to suggest, please let met know. Thank you so much for that comment Qiaochu! – mathguy Aug 2 '12 at 4:38