Skip to main content
1 of 5
Cauchy
  • 153
  • 6

k nearest neighbors sensitivity

Assume $n$ points $P_i \in \mathbb{R}^2, i \in {1,2,...,n}$. For each point there is a $k$ nearest neighbor $(k<n)$, or equivalently for each point $P_i$ there is one circle with center the point $Pi$ and radius $r_i$ such that the circle contains exactly $k+1$ points (considering also the center $Pi$). The questions is what is maximum number of circles that a point can participate?

For one nearest neighbor ($k=1$) and by using the properties of regular hexagon I can prove that the maximum number is 5 (less than 6). Is there any way to extend it for $k>1$?

Cauchy
  • 153
  • 6