Re: K-nearest neighbhors on an equispaced multidimensional grid

• To: mathgroup at smc.vnet.net
• Subject: [mg72036] Re: K-nearest neighbhors on an equispaced multidimensional grid
• From: "Ray Koopman" <koopman at sfu.ca>
• Date: Sat, 9 Dec 2006 06:09:44 -0500 (EST)
• References: <elbij5\$k7o\$1@smc.vnet.net>

```erwann.rogard at gmail.com wrote:
> hi,
>
> i am looking for an algorithm/data structure to find the K-nearest
> neighbors on an equispaced multidimensional grid.
>
> x=(x_1,...,x_D) where x_d takes values in (...,-1,0,1,...)  for all
> d=1,...,D
>
> for example if D=2 and x=(0,0) the
>
> 1-NN is x itself
> 5-NN are x, (-1,0), (0,-1),(1,0),(0,1)
> 9-NN are x, (-1,0), (0,-1),(1,0),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)
>
> etc...
>
> thanks,
>
> e.

Let X be an m-dimensional equispaced grid on -k,...,k:

In[1]:= X = With[{k = 1, m = 2}, Tuples[Range[-k,k], m]]

Out[1]= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}}

Pick a random point x from X:

In[2]:= x = X[[Random[Integer,{1,Length@X}]]]

Out[2]= {0,-1}

Prepend each point's squared distance from x to its coordinates:

In[3]:= Prepend[#, (#-x).(#-x)]& /@ X

Out[3]= {{1,-1,-1},{2,-1,0},{5,-1,1},{0,0,-1},{1,0,0},{4,0,1},
{1,1,-1},{2,1,0},{5,1,1}}

Sort the points in terms of their distances from x:

In[4]:= Sort[%]

Out[4]= {{0,0,-1},{1,-1,-1},{1,0,0},{1,1,-1},{2,-1,0},{2,1,0},
{4,0,1},{5,-1,1},{5,1,1}}

Group the points in terms of their distances from x:

In[5]:= Split[%, #1[[1]] == #2[[1]] &]

Out[5]= {{{0,0,-1}},{{1,-1,-1},{1,0,0},{1,1,-1}},{{2,-1,0},{2,1,0}},
{{4,0,1}},{{5,-1,1},{5,1,1}}}

Extract the squared distances and insert them as headers:

In[6]:= {#[[1,1]], Rest/@#}& /@ %

Out[6]= {{0,{{0,-1}}},
{1,{{-1,-1},{0,0},{1,-1}}},
{2,{{-1,0},{1,0}}},{4,{{0,1}}},
{5,{{-1,1},{1,1}}}}

Here it is all together, given X and x:

In[7]:= {#[[1,1]], Rest/@#}& /@ Split[Sort[Prepend[#, (#-x).(#-x)]&
/@ X], #1[[1]] == #2[[1]] &]

Out[7]= {{0,{{0,-1}}},
{1,{{-1,-1},{0,0},{1,-1}}},
{2,{{-1,0},{1,0}}},{4,{{0,1}}},
{5,{{-1,1},{1,1}}}}

```

• Prev by Date: Re: Re: Finding the periphery of a region
• Next by Date: Re: Solve chokes on Piecewise input that Reduce handles quite well??
• Previous by thread: K-nearest neighbhors on an equispaced multidimensional grid
• Next by thread: Re: K-nearest neighbhors on an equispaced multidimensional grid