9
$\begingroup$

Let $d$ be a positive integer, and let $\mathbb{R}^d$ be endowed with the Euclidean metric. Given an infinite set $S \subset \mathbb{R}^d$ without limit points and a positive integer $n$, is there always a point $p \in \mathbb{R}^d$ and a radius $r \in \mathbb{R}^+$ such that the $r$-neighbourhood of $p$ contains exactly $n$ points in $S$?

If the answer is yes, what can be said in general about in which metric spaces this holds?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ It is impossible for metric trees. The same argument as Andre's shows that it is possible in the case of connected Riemannian manifolds. $\endgroup$
    – Misha
    Commented Jan 9, 2014 at 22:37

1 Answer 1

Reset to default
13
$\begingroup$

Yes, this is possible.

Pick $p$ generic, so that $$\not \exists\,\,\, x,y\in S\quad\text{s.t.}\quad d(p,x)=d(p,y).$$

Then slowly increase the radius until the $r$-neighborhood of $p$ contains exactly $n$ points of $S$.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Does the argument hold in $Q^d$? That is, how one would show that it's always possible to pick $p\in Q^d$ non-equidistant from $x,y\in S$? $\endgroup$
    – Michael
    Commented Jan 9, 2014 at 23:24
  • $\begingroup$ Thanks. -- That answers the first question (and also shows that one probably shouldn't ask questions which are too far off one's area of expertise!). $\endgroup$
    – Stefan Kohl ♦
    Commented Jan 10, 2014 at 0:18
  • 2
    $\begingroup$ @Michael: No, $\mathbb{Q}^d$ is countable. Take an enumeration of the points, and eliminate each one by adding a pair of points to $S$ at the same distance from that point. These pairs can be chose so that there is no limit point of $S$, say by making the distance from the origin be at least $i$ for each point of the $i$th pair added. Some other argument may work to enclose $n$ points, but you can't just choose a generic center and expand a sphere about this center. $\endgroup$
    – Douglas Zare
    Commented Jan 10, 2014 at 0:29
  • 5
    $\begingroup$ Take a disc that encloses much more than n points. Find a point in $\mathbb Q^d$ very close to the center of the disc which is generic with respect to all the points of the disc. Then choose a radius such that only n points in the disc are in that radius. If the new center is sufficiently close to original center, all points in the new disc will be in the old disc, because the new radius is smaller. $\endgroup$
    – Will Sawin
    Commented Jan 10, 2014 at 2:16

You must log in to answer this question.

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