Geek Answers Handbook

How does the space sharing algorithm work for finding nearest neighbors?

To find the closest neighbor, Space Partitioning is one of the algorithms. How it works?

Suppose I have a two-dimensional set of points (x and y coordinates), and I am given a point (a, b). How does this algorithm detect the nearest neighbor?

+4
source share
2 answers

Separation partitioning is actually a family of closely related algorithms that divide the space so that applications can more easily handle points or polygons.

I believe that there are many ways to solve your problem. I do not know how ready you are to build your decision. A simple way would probably be to build a binary tree dividing the space into 2. All points divided between some middle plane. Build your tree by dividing recursively until you finish the points.

The search for the nearest neighbor will be optimized, because each traversal of the tree narrows the scope of the search.

In some literature they call it kd tree

+4
source

These two videos should help:

+2
source

More articles:


All Articles