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'Rourke Oct 4 '11 at 1:30
  • $\begingroup$ I think it'll be better to consider the average $F(X)/n$ instead of $F(X)$. $\endgroup$ – Suvrit Oct 4 '11 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 Ivanov Oct 4 '11 at 14:04
  • $\begingroup$ I clarified what I meant by "related" in the problem statement. Thanks. $\endgroup$ – Joord Jacobsen Oct 4 '11 at 18:21

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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