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?



Bounding number of $k$-nearest neighbor sets in $\mathbb{R}^d$
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. 


