Let $X = \{x_1, \dots, x_n\}$ denote a finite set of $n$ points in the unit square $S$, and let's center $S$ at the origin. Let $F(X) = \sum_{i=1}^n \| x_i \| $ and let $G(X) = \iint_S \min_i \|x - x_i\|~ dA $ be the average distance between a uniformly sampled point in $S$ and its nearest neighbor in $X$. Clearly $F(X)$ increases as $n$ becomes larger and $G(X)$ decreases. For any given configuration $X$, how are these two quantities related (e.g. orders of magnitude)? More specifically I'd like to relate these two quantities via inequalities; for example, if $G(X)$ is small, it must mean that the points are somewhat uniformly distributed in $S$, and therefore their average distance from the origin should be somewhere between $1/2$ and $\sqrt{2}/2$. On the other hand if $F(X)$ is small then it means all of the points are packed close to the origin, so $G(X)$ must be fairly large, regardless of $n$.
-
$\begingroup$ The answers and comments to this MO question may help: "Mean minimum distance for $k$ random points on a $n$-dimensional hypercube": mathoverflow.net/questions/22592 $\endgroup$– Joseph O'RourkeCommented Oct 4, 2011 at 1:30
-
$\begingroup$ I think it'll be better to consider the average $F(X)/n$ instead of $F(X)$. $\endgroup$– SuvritCommented Oct 4, 2011 at 13:00
-
$\begingroup$ What kind of relation do you expect? If the points are packed into a small region, $F(X)$ can be anything from 0 to $\sim N$, depending on how far this region is from the origin, and $G(X)$ will be around 1 (and not depending on $N$). $\endgroup$– Sergei IvanovCommented Oct 4, 2011 at 14:04
-
$\begingroup$ I clarified what I meant by "related" in the problem statement. Thanks. $\endgroup$– Joord JacobsenCommented Oct 4, 2011 at 18:21
1 Answer
One can show that $F(X)> c\cdot G(X)^{-2}$ for some $c>0$, provided that $G(X)$ is sufficiently small.
Let $G(X)=\varepsilon$. Divide the square into $\approx(100\varepsilon)^{-2}$ small squares of size $100\varepsilon\times 100\varepsilon$. At least 9/10 of these squares must contain points of $X$. Indeed, if a $100\varepsilon\times 100\varepsilon$ square does not contain points of $X$, then it contributes at least $10\varepsilon(100\varepsilon)^{2}$ to the integral of the minimum distance, so one can afford only $(100\varepsilon)^{-2}/10$ such "empty" squares. Given that many non-empty squares, at least half of them are separated by the distance at least 1/10 from the origin and thus contribute at least $c\varepsilon^{-2}$ to $F(X)$.
You get $F(X)\sim c\epsilon^{-2}$ if you choose $X$ to be a uniformly packed $\varepsilon$-net. And then you can enlarge $F(X)$ arbitrarily by adding many copies of some point (not at the origin). So you cannot get anything beyond the inequality $F(X)> c\cdot G(X)^{-2}$, at least in terms of orders of magnitude.
