Thread replies: 7
Thread images: 1
Thread images: 1
File: 7UzjUF1M.jpg (19KB, 720x720px) Image search:
[Google]
19KB, 720x720px
came up with an algorithem to go over a list of 2d points and match each point to it's closest point with great efficiency.(nearest neighbor search for 2d)
need a way to genrealize this algorithem to higher dimensions.
basically the brute force way of O(n^2) is for each point go over all other points and find the closest point.
my method is to first sort the list by the point x value (each point is represented as (x,y)).
if for some point p1 I know of some minimum distance d to some other point p2, then if the difference between some point p3 x value and
p1 x value is greater than d, then the distance between p3 and p1 must be greater than he distance between p2 and p1.
using this I would only need to go over few points until I know what the minimum distance point is, instead of the whole list.
python code for you to inspect:
https://gist.github.com/anonymous/35746facfe07f4ed9078eebd39df162b
problem is, I need a way to generalize it to higher dimensions reliably
>>
>>56436480
>>>/homework/
>>
>>56436480
You should check if the distance is greater than d^2:
d(p1,p2) = \sqrt{ \sum_{i = 1}^{N} (x^{1}_{i} - x^{2}_{i})^{2} }
Now let p3 =\{ x^^{3}_{j} \}_{j=1}^{N}. If
x^{1}_{k} - x^{3}_{k} > d(p1,p2)^2
then
d(p1,p3)^{2} = \sum_{i = 1}^{N} (x^{1}_{i} - x^{3}_{i})^{2} = x^{1}_{k} - x^{3}_{k} + \sum_{i = 1 , j \neq k }^{N} (x^{1}_{i} - x^{3}_{i})^{2} > d(p1,p2)^{2} + \sum_{i = 1 , j \neq k }^{N} (x^{1}_{i} - x^{3}_{i})^{2} > d(p1,p2)^{2}
Therefore, d(p1,p3) > d(p1,p2).
>>
>>56436480
best way is to use a proper data structure like kdtree
>>
>>56436480
I bet this would be faster in python with numpydef find_closest(unarranged_array, index):
unarranged -= unarranged[index]
distances = sum((unarranged*unarranged).transpose())
return distances.index(np.partition(distances,1)[1])
but maybe you are just interested in the theory.
>>
>>56436746
yeah, I am
>>
>>56436597
Nevermind, I'm an idiot. d is fine. If
x^{1}_{k} - x^{3}_{k} > d(p1,p2)
Then
(x^{1}_{k} - x^{3}_{k})^{2} > d(p1,p2)^{2}
Thread posts: 7
Thread images: 1
Thread images: 1