MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
The answers and comments to this MO question may help: "Mean minimum distance for $k$ random points on a $n$-dimensional hypercube": – Joseph O'Rourke Oct 4 '11 at 1:30
I think it'll be better to consider the average $F(X)/n$ instead of $F(X)$. – Suvrit Oct 4 '11 at 13:00
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$). – Sergei Ivanov Oct 4 '11 at 14:04
I clarified what I meant by "related" in the problem statement. Thanks. – Joord Jacobsen Oct 4 '11 at 18:21
up vote 3 down vote accepted

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.

share|cite|improve this answer
Thanks! Just what I was looking for. – Joord Jacobsen Oct 5 '11 at 3:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.