Consider $n$ adversarially chosen points in $\mathbb{R}^{d}$ where $n \gg d$. Let $\mathbf{a}$ be one of the $n$ points. Is there an upper bound on the number of points among the remaining $n-1$ points, that can have $\mathbf{a}$ as the nearest neighbor?

It is easy to see that if $\mathbf{a}$ is the nearest neighbor for both $\mathbf{b}$ and $\mathbf{c}$, then if a triangle is drawn with these three points, the angle subtended at $\mathbf{a}$ is at least $60$ degrees.

  • 4
    $\begingroup$ Seems then that you're basically looking for the kissing number in that dimension (at least if you allow ties). en.wikipedia.org/wiki/Kissing_number_problem $\endgroup$ Mar 31 '17 at 2:33
  • $\begingroup$ Thanks. I can almost see the connection. But I cannot yet prove it that the kissing number is exactly the quantity of interest (supposing I allow for ties). Sorry I am a bit slow today. $\endgroup$
    – rajatsen91
    Mar 31 '17 at 3:05
  • 4
    $\begingroup$ Well by your observation if a is the point with many neighbors b then the vectors (b-a) / || b-a || form a kissing configuration; and conversely such a configuration around a gives a as many neighbors as the kissing number. $\endgroup$ Mar 31 '17 at 3:11
  • $\begingroup$ You're welcome. I'm surprised that this question was closed, because it's equivalent to a standard open (and probably very hard) problem. But then the demonstration of such an equivalence is deemed tantamount to an answer here, and so the question has now been answered in the comments. $\endgroup$ Mar 31 '17 at 16:10