Question

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$.

Answer 1

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.