2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't understand the sentence defining the $k$-NN set. $\endgroup$
    – YCor
    Commented Jun 17, 2017 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
    Commented Jun 17, 2017 at 2:07
  • $\begingroup$ Added clarifications. Apologies for any confusions! $\endgroup$
    – heinrich
    Commented Jun 17, 2017 at 4:23

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .