How can I use the nearest neighbor search algorithms to search for a fixed radius?

Question

There are many works for finding the nearest neighbor, so I wonder if I want to do a fixed search for the range of radius , can I use these algorithms for finding the nearest neighbor?

perhaps I could repeat the search for the kth closest neighbor again and again until I find a point outside the radius, but I suppose this can cause a lot of waste.

Answer 1

Not only "There are many jobs to find your closest neighbor," but there are many questions you need to ask for your problem. The most important is the number of measurements.

Make sure you check my answer if you are not sure about the importance of the measurement.

---

High space

Assuming your points are in a high-dimensional space, you should go Locality-Sensitive Hashing (LSH) . A good implementation of this algorithm is E²LSH . They also provide slides if you want to implement it yourself or better understand what is happening. Note that E²LSH solves a randomized version of the R-near neighborhood problem, which they call the (R, 1 - δ) -independent problem, where δ is related to approximation, as they note in manual .

You can also check my answer regarding LSH here . I used it in C ++ and I highly recommend it for finding a fixed radius that you want to execute!

---

Small space

Use CGAL spatial search . I have used it many times for this case in C ++. Again, if you want to realize yourself, you can find a lot of information in the good documentation that they have and fulfill relative Google searches.

---

Good answer, by the way, so you got my +1. :)

Answer 2

If you have only one request, then this problem will be fixed by O (n), where n is the number of points no matter what.

If you have multiple requests, this problem has been well studied, but the solution is more complicated than finding the nearest neighbor. See this article: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.3191&rep=rep1&type=pdf

Answer 3

Taking d as the number of dimensions and r as the radius, I know at least two different approaches that you can use:

Using a spatial hash:

Imagine a task space divided into hypercubes by a grid of size s such that s = r / sqrt(d) .

The interesting thing about s = r / sqrt(d) is that any two points inside a hypercube of this size are guaranteed to be at a distance equal to or less than r .

You can number the grid divisions so that each hypercube can be identified by a tuple formed by the indices of one of its angles. These index tuples can be used as keys in a hash structure (spatial hash).

Now, and this is the difficult part, you should notice that for any hypercube of grid A there are many neighboring hypercubes N = (N1, N2, ...) whose minimum distance to a given hypercube is equal to or less than a given radius, geometrically they look like a hypersphere . Elements of the set N can be represented as deltas associated with the grid indices, with A Note that these delta indices depend only on d .

For example, in the two-dimensional case, you have the following geometric structure:

  NNN index deltas: (-1, 2) ( 0, 2) ( 1, 2) NNNNN (-2, 1) (-1, 1) ( 0, 1) ( 1, 1) ( 2, 1) NNANN (-2, 0) (-1, 0) ( 0, 0) ( 1, 0) ( 2, 0) NNNNN (-2, -1) (-1, -1) ( 0, -1) ( 1, -1) ( 2, -1) NNN (-1, -2) ( 0, -2) ( 1, -2) 

So, you already have everything you need to effectively search for points within the hypersphere:

• Press the entry points into the spatial hash using the index cube of the hypercube containing them as a key.

• For point p search method is to determine the hypercube where it lies A , and then, using the set of delta indices, obtain a set of neighbor hypercubes N , which can potentially contain points closer than r .

• Extract points belonging to the hypercubes N from the spatial hash and check which ones are sufficiently close to p .

There are several additional optimizations that can be performed because they do not check the points in A, since they are guaranteed to be close enough. Pre-filtering N can be performed depending on the position of p relative to A

Note that choosing s = r / sqrt(d) provides a good compromise between having small hypercubes and a not-too-large set of N

Using the kd tree or quad / octo /...- tree:

Each time you go down one level in the tree, you check to see if it crosses the space with the query hypersphere. If so, you continue to decline, otherwise you completely drop it in search.