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$?


2 Answers 2


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).

  • $\begingroup$ The difference foes not matter too much: if there is a point belonging to $D$ $k$-neighboring balls, you may just include it into the set of the $P_i$; after that, it will still belong to $k$-neighboring balls centered at the same points. $\endgroup$ Oct 15, 2016 at 13:57

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$.

  • $\begingroup$ For a regular pentagon $L>d(p,q_i)$ is that correct or am I missing something? $\endgroup$
    – Cauchy
    Mar 1, 2016 at 3:15
  • $\begingroup$ Also I used a neighborhood close to $q_1$, instead of $d(q_1,s_1m)$ to place the $k-1$ points. $\endgroup$
    – Cauchy
    Mar 1, 2016 at 3:28
  • $\begingroup$ The construction can be stated quite simply: Put $k$ points near each vertex of a regular pentagon, and one in the center. $\endgroup$ Mar 1, 2016 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.