<p>In Handbook of discrete and computational geometry (Goodman and Rourke eds.), there is a chapter on the complexity of knn search. I do not remember the complexities discussed there, for the high dimensional cases, but they are effectively not "miraculous".</p>

<p>The subset sum problem can be converted quite easily to a knn search on lp norms, this may hint at why there seems to be a research problematic.</p>

<p>You can use the fundamental theorem of arithmetic to map d-dimensional point to the line and then use a variant of binary search for intervals... And do some additional work...</p>

CC BY-SA 3.0
2013-07-25T05:44:27.097Z
I think single point knn queries and all points knn are subtly different.
Simd
CC BY-SA 3.0
2013-07-25T13:11:36.747Z
Single point knn when the query is the 0-vector is equivalent to searching a list of norms. Now if you have N possible queries, you can normalize your data to the N queries each of which are now the new origin of the system. This yields an N-dimensional list of numbers, like a distance matrix... If N tends to infinity, you get a manifold...
Phil
CC BY-SA 3.0
2013-07-25T02:09:23.247Z
2013-07-25T02:09:23.247Z
Phil
<p>$O(kn+n\log n)$. See</p>

<p>P.B. Callahan, S.R. Kosaraju, A decomposition of multidimensional
point sets with applications to <em>k</em>-nearest-neighbors and <em>n</em>-body potential ﬁelds, <em>J. ACM</em> 42 (1995) 67–90.</p>

<p>In some models of computation the $O(n\log n)$ part can be reduced or removed; see also</p>

<p>T. M. Chan, Well-separated pair decomposition in linear time?, <em>Inf. Proc. Lett.</em> 2008.</p>

CC BY-SA 3.0
2013-07-18T21:06:45.867Z
Thank you. As I would like to implement a solution, do you have a feeling for which of the existing methods is practical? Searching using your answer gives quite a few options.
Simd
CC BY-SA 3.0
2013-07-18T20:03:22.073Z
2013-07-18T20:03:22.073Z
David Eppstein
<p>If you have n points in 2d space, how quickly can you report the k nearest points to every point under Euclidean distance? If it helps speed things up we can ignore points that are more than some distance away as well so potentially return fewer than k. A randomized or approximate solution would also be interesting.</p>

<p>One solution is to build a kd tree and do an independent look up for every point. Is this as good as it gets?</p>

<ds.algorithms>
Finding k nearest neighbors for all points
Simd
# Finding k nearest neighbors for all points

(Asked by: username_0 on 2013-07-18)

If you have n points in 2d space, how quickly can you report the k nearest points to every point under Euclidean distance? If it helps speed things up we can ignore points that are more than some distance away as well so potentially return fewer than k. A randomized or approximate solution would also be interesting.

One solution is to build a kd tree and do an independent look up for every point. Is this as good as it gets?

**Tags:** ds.algorithms

---

## 2 answers

### Answer by username_2 on 2013-07-18. Score: 10 | Accepted answer

$O(kn+n\log n)$. See

P.B. Callahan, S.R. Kosaraju, A decomposition of multidimensional
point sets with applications to *k*-nearest-neighbors and *n*-body potential ﬁelds, *J. ACM* 42 (1995) 67–90.

In some models of computation the $O(n\log n)$ part can be reduced or removed; see also

T. M. Chan, Well-separated pair decomposition in linear time?, *Inf. Proc. Lett.* 2008.

> **Comments:**
> **username_0**: Thank you. As I would like to implement a solution, do you have a feeling for which of the existing methods is practical? Searching using your answer gives quite a few options.  

---

### Answer by username_1 on 2013-07-25. Score: 0

In Handbook of discrete and computational geometry (Goodman and Rourke eds.), there is a chapter on the complexity of knn search. I do not remember the complexities discussed there, for the high dimensional cases, but they are effectively not "miraculous".

The subset sum problem can be converted quite easily to a knn search on lp norms, this may hint at why there seems to be a research problematic.

You can use the fundamental theorem of arithmetic to map d-dimensional point to the line and then use a variant of binary search for intervals... And do some additional work...

> **Comments:**
> **username_0**: I think single point knn queries and all points knn are subtly different.  
> **username_1**: Single point knn when the query is the 0-vector is equivalent to searching a list of norms. Now if you have N possible queries, you can normalize your data to the N queries each of which are now the new origin of the system. This yields an N-dimensional list of numbers, like a distance matrix... If N tends to infinity, you get a manifold...  

---

