# Bounding number of $k$-nearest neighbor sets in $\mathbb{R}^d$

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?

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