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

This question is a follow-up on a previous question I asked at:

Distances between and among points in a region

Let $X = x_1,\dots,x_n$ denote a finite set of $n$ points in the unit circle $C$ in the plane. Let $F(X)=\sum_{i=1}^{n} \|x_i\|^2$ and let $G(X) = \iint_{C} \min_i\|x - x_i\| dx $ be the average distance between a uniformly sampled point in $C$ and its nearest neighbor in $X$. Let's consider the problem of choosing $X$ (whose cardinality, $n$, may also vary) so as to minimize $G(X)$, subject to the constraint that $F(X) \leq a$ for some constant $a$. Clearly as $a$ goes to infinity, the cardinality of $X$ will increase. My question: let $X^{*}(a)$ denote the optimal solution to the preceding problem for fixed $a$ (which is not unique up to rotation about the origin, obviously, and may not be unique for other reasons as well). As $a\rightarrow\infty$, can we choose point sets $X^{*}(a)$ that "converge" to a probability distribution? That is, does there exist a probability density $f(x)$ on $C$ such that, for any measurable region $R\in C$, we have

$ \frac{ \#( x_i^{*}(a) \in R ) }{ \#( X_i^{*}(a) ) } \rightarrow \iint_R f(x) dx$

as $a\rightarrow\infty$? More concisely, "does the optimal solution $X^{*}(a)$ have to converge to anything?

(I am not inquiring about what the distribution $f(x)$ is; I just want to prove such a distribution exists, which seems intuitively true)

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.