Fix $A:=\{x_1,.x_2,...x_m\}\in \mathbf{R^n}$. Given a point $v\in \mathbf{R}^n$, let $N_k(v)\subset A$ be the set of k nearest points to $v$ in $A$. How many different $N_k(v)$ as $v$ varies? Of course $\binom{m}{k}$ is an upper bound, but is there a tighter one?
I think it is equivalent to the following question: How many different subsets $B\subset A$ with k elements such that there exists a hyperplane separates $B$ and $A\setminus B$.(i.e. there is a linear functional $f$ such that $f(x)>0$ for any $x\in B$, and $f(x)<0$ for any $x\in A\setminus B$).
Is there any theory about this question?