How to find the k-th nearest neighbor of a point in a set of points

Question

I have a set of points (x, y) on the 2d plane. For the point (x0, y0) and the number k, we find the kth nearest neighbor (x0, x0) in the set of points. In detail, a set of points is represented by two arrays: x and y. The point (x0, y0) is given by the index i0. This means that x0 = x (i0) and y0 = y (i0).

Is there any function or something in Matlab this problem helps me. If Matlab does not have such a feature, can you suggest other effective ways.

EDIT : I need to calculate this kind of distance for each point (x0, y0) in the set. The set size is about 1000. The value of k should be around sqrt (1500). The worst part is that I do it many times. At each iteration, the set changes, and again I calculate the distances. Thus, runtime is a critical issue.

Answer 1

if you do this check for many points, you can first create a table of distances between points

squareform(pdist([xy])) 

Answer 2

If you have a statistics toolbar, you can use the knnsearch function.

Answer 3

The brute force algorithm would be something like this:

 array x[n] = () array y[n] = () array d[n] = () ... populate x and y arrays with your n points ... /* step over each point and calculate its distance from (x0, y0) */ for i = 1 to n do d[i] = distance((x0, y0), (x[i], y[i]) end /* sort the distances in increasing order */ sort(d) /* the k'th element of d, is the k'th nearest point to (x0, y0) */ return d[k] 

Answer 4

The brute force approach looks something like this:

 %Create some points n = 10; x = randn(n,1); y = randn(n,1); %Choose x0 ix0 = randi(n); %Get distances d = sqrt(... (x - x(ix0) ).^2 + ... (y - y(ix0) ).^2 ); %Sort distances [sorted_Dstances, ixSort] = sort(d); %Get kth point k = 3; kth = [x(ixSort(k+1)); y(ixSort(k+1))]; %+1 since the first element will always be the x0 element. 

Answer 5

The free and openource VLFeat toolbox contains an implementation of the kd tree, among other useful things.