k nearest points

Question

Assume $n$ points $P_i \in \mathbb{R}^2, i \in {1,2,...,n}$. For each point there is a $k$ nearest neighbour $(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 question 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$?

Answer 1

What you're asking is: what is the ply of the system of $k$-nearest-neighbor balls? Here the ply is the maximum number of balls that have a common intersection. It's not quite the same as the degree of the $k$-nearest-neighbor graph (Fischler's answer) because the ply can be maximized at a point that's not one of the given ones.

Anyway, it is known that in any dimension the ply is at most $\tau k$, where $\tau$ is the kissing number; this is only slightly weaker than the bound given by Fischler's answer. See e.g. Separators for sphere-packings and nearest neighbor graphs, Miller et al., JACM 1997 (p.16 of the preprint version).

Answer 2

The answer is that a point $p$ can participate in $5k$ circles. The construction demonstrating that $p$ can be in $5k$ circles (that is, it can be the 5-th nearest neighbor to $5k$ other points) is as follows:

Place $p$ at the center of a regular pentagon of side length $L$. Place $q_1$ at one of the vertices; draw a circle $C_1$ centered at $q_1$ with radius $r_1 = d(p,q_1) + \epsilon_1$ (for some small positive $\epsilon_1$).

Now mark the point $t_1$ on the line from $p$ to $q_1$ such that $d(p,t_1) = L$. And place $k-1$ points $\{ s_{11}, s_{12}\ldots\}$ along the line from $q_1$ to $p$ such that $$d(q_1, s_{1m}) = 2^{-m}(d(q_1,p)-\epsilon_1) $$ and commit to placing no other points inside $C_1$. Then for all $m, j < k$, $$d(s_1m,s_1j) < d(p, s_1m) \mbox{ and } d(q_1,s_1m,) < d(p, s_1m). $$

Thus (since we will not put any other points inside $C_1$) $p$ is the $k$-th nearest neighbor to each of the $k$ points $\{q_1, s_{11}, s_{12} \ldots \}$.

Now place $q_2$ at a neighboring vertex of the pentagon, and construct $C_2$ centered at $q_2$ with radius $r_2 = d(p,q_2) + \epsilon_2$. While the line from $q_2$ to $p$ does intersect with the interior of $C_1$, the part of that line starting at $q_2$ and extending to length $\frac12 (d(p,q_2)-L)$ does not intersect $C_1$. Thus all the $s_{2m}$ are farther from all the $s_{1m}$ than they are from each other or from $p$ or $q_1$, and by the same argument as before, $p$ is the $k$-th nearest neighbor to each of the $k$ points $\{q_2, s_{21}, s_{22} \ldots \}$.

Proceed in this fashion to place all five $q_j$, and you have constructed $p$ to be the $k$th nearest neighbor to each of $5k$ other points.

Now, can we place $q$ to be the $k$-th nearest neighbor to at least $5k+1$ other points? The same reasoning that prevents (without allowing ties) a point from being the nearest neighbor to $6$ other points also prevents tightening the angular distances between the groups of $s_{1m}$ and $s_{2m}$, and we obviously could add no additional points on the line segments without dropping one of the $q_i$ from the list of points having $p$ as a $k$-th nearest neighbor. So the only approach to increasing the number would be to stagger the $s_{im}$ in angle, to try to make room for another point.

I have a rather long and ugly proof that for $k=2$ you cannot be the second nearest neighbor to more than $10$ other points. The underlying reason is again that a (convex) hexagon must contain two points that are closer together than the distance between one of those points and a specified point in the interior.

But I can't seem to handle the general case for $k>2$.