Suppose that $\mathcal{X} \subseteq \mathbb{R}^d$ is compact.

Let there be $n$ distinct points $X = \{ x_1,...,x_n \} \subseteq \mathcal{X}$ and $k = \lfloor n^\alpha \rfloor$ where $0 < \alpha < 1$. Assume $\alpha$ and $d$ are fixed.

Define the $k$-NN radius of $x \in \mathcal{X}$ as $r_k(x) := \inf \{ r : |B(x, r) \cap X| \ge k \}$ where $B(a, r) := \{a' \in \mathcal{X} : |a - a'| \le r \}$.

Define the $k$-NN set of $x \in \mathcal{X}$ to be $N_k(x) := X \cap B(x, r_k(x))$. This can be viewed as the $k$ closest points in $X$ to $x$ (unless there are ties).

Let $M$ be the number of distinct $k$-NN sets over $\mathcal{X}$, that is, $M := |\{ N_k(x) : x \in \mathcal{X} \}|$.

Is $M$ bounded polynomially in $n$?

If not, then if we assume $X$ is sampled i.i.d. from some distribution, then do we at least have $M = O(poly(n))$ with high probability?

  • $\begingroup$ I don't understand the sentence defining the $k$-NN set. $\endgroup$ – YCor Jun 17 '17 at 1:27
  • $\begingroup$ What are you going to do if $x$ is the origin and $\mathcal X$ is the unit sphere together with the origin? $\endgroup$ – fedja Jun 17 '17 at 2:07
  • $\begingroup$ Added clarifications. Apologies for any confusions! $\endgroup$ – heinrich Jun 17 '17 at 4:23

Yes, it is polynomially bounded in $n$, since $\binom{n}2$ perpendicular bisectors to the pairs of points from $X$ partition $\mathbb{R}^d$ onto polynomially many parts.


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.