K-nearest neighbor in 2D dimension space
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.
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
Grid version algorithm:
Apply algorithm described above.
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.
O(n log n)