Software Programming

Kunuk Nykjaer

K-nearest neighbor in 2D dimension space

with 4 comments

K-nearest neighbor

There are miscellaneous algorithms for searching nearest neighbors.

An alternative method is to use grid indexing strategy.
Slowly expand the grid boxes from the center to find the k-nearest neighbors.
The grid is used as a filtering mechanism to reduce the search space.

This works fast for distributed data across the space and is a good alternative algorithm for dynamic data that changes position frequently.

Reference links:

Project implemented in C# is available at Github:
A survey of techniques for fixed radius near neighbor searching:


The origin is in ring 0.
The origin can anywhere in the box and the distance to test on first iteration must be at least 1 x grid distance. The first iteration starts with data from ring 0 and 1.

The algorithm goes like this:

i = 0
Point origin
list currRing = empty
list nextRing = empty
list temp
while all rings not explored
   i = i + 1
   temp = empty
   for all point in nextRing test distance between origin and point
       if distance is within i * grid put it in currRing
       else put it in temp

   nextRing = empty
   Add all from temp to nextRing

   temp = empty
   if(i==1) temp = points from ring 0 and ring 1
   else temp = points from ring i

   For all point in temp test distance between origin and point
       if distance is within i * grid put it in currRing
       else put it in nextRing

   If there are at least k points in currRing then exit while loop
end while loop

if currRing count is < k then add all from nextRing to currRing

sort currRing by distance
take first k from currRing

knn example

Grid version algorithm:
Apply algorithm described above.
Searching: O(n * m) where m is grid cells and k << n.

Naive version algorithm:
For origin point check the distance to every other point.
Take k first items sorted by distance.
Searching: O(n log n)

Written by kunuk Nykjaer

January 21, 2013 at 9:36 pm

4 Responses

Subscribe to comments with RSS.

  1. Good day! Would you mind if I share your blog with my zynga group?
    There’s a lot of folks that I think would really appreciate your content. Please let me know. Thank you


    February 21, 2013 at 12:09 am

  2. hello
    can you give me your mail address or contact information, i have a problem to ask from you.


    October 7, 2014 at 9:57 pm

  3. Nice weblog right here! Additionally your website rather a lot up fast!

    What web host are you using? Can I am getting your associate link in your host?
    I want my web site loaded up as quickly as yours lol

    mother exericse

    September 26, 2018 at 12:36 am

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: