Proving that an optimal solution "converges" - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T19:00:58Z http://mathoverflow.net/feeds/question/86324 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/86324/proving-that-an-optimal-solution-converges Proving that an optimal solution "converges" Joord Jacobsen 2012-01-21T19:20:40Z 2012-01-21T19:34:47Z <p>This question is a follow-up on a previous question I asked at:</p> <p><a href="http://mathoverflow.net/questions/77088/distances-between-and-among-points-in-a-region" rel="nofollow">http://mathoverflow.net/questions/77088/distances-between-and-among-points-in-a-region</a></p> <p>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 <code>$X^{*}(a)$</code> 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</p> <p><code>$\frac{ \#( x_i^{*}(a) \in R ) }{ \#( X_i^{*}(a) ) } \rightarrow \iint_R f(x) dx$</code></p> <p>as $a\rightarrow\infty$? More concisely, "does the optimal solution $X^{*}(a)$ have to converge to anything?</p> <p>(I am not inquiring about what the distribution $f(x)$ is; I just want to prove such a distribution exists, which seems intuitively true)</p>