2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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$
    – Noam D. Elkies
    Commented Mar 31, 2017 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
    Commented Mar 31, 2017 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$
    – Noam D. Elkies
    Commented Mar 31, 2017 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$
    – Noam D. Elkies
    Commented Mar 31, 2017 at 16:10

0

Reset to default