User joord jacobsen - MathOverflow

Proving that an optimal solution "converges"

2012-01-21T19:20:40Z

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

http://mathoverflow.net/questions/77088/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)

Weighted area of a Voronoi cell

2011-10-14T06:37:43Z

Let $X = { x_1,\dots,x_n} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = {w_1,\dots,w_n}$ denote a set of weights corresponding to the $n$ points in $X$. Define the "power diagram" of $X$ in $S$ to be a partition of $S$ into at most $n$ pieces $V_i$, where

$V_i = {x\in S: \|x - x_i\|^2 + w_i \leq \|x - x_j\|^2 + w_j \forall j \neq i }$

i.e. a "weighted Voronoi diagram". Now let's consider varying the weight $w_1$ while fixing the other weights; specifically, consider the function

$f(w_1) = w_1\cdot \text{Area}(V_1)$

Clearly as $w_1 \rightarrow 0$ we have $f(w_1) \rightarrow 0$ and as $w_1 \rightarrow \infty$ we have $f(w_1) \rightarrow 0$ as well. My question: is $f(w_1)$ unimodal? Convex? Is the answer different if I only have $n=2$ points? What if I define my cells slightly differently, such as

$V_i = {x\in S: \|x - x_i\| + w_i \leq \|x - x_j\| + w_j \forall j \neq i }$ ?

Distances between and among points in a region

2011-10-03T23:51:34Z

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

Integrating with sub-level sets

2011-09-16T17:32:55Z

This is a simple question, and I'm sure it was a homework assignment at some point (assuming it's true) but it's one that I'm puzzled over. Suppose I have a compact domain $D \subset \mathbb{R}^n$ with area $1$ and a continuous, bounded function $g(x):D\rightarrow\mathbb{R}$. Let $F(t)$ denote the volume of the subset of $D$ on which $g(x) \leq t$; since the volume of $D$ is $1$ this means that we can think of $F(t)$ as a cumulative distribution function, and we can differentiate this (assuming whatever smoothness properties are necessary) to obtain a pdf $f(t)$. Is it true that

$\iint_D g(x) dA = \int_0^c t f(t) dt $

where $c = \max_{x\in D} g(x)$? In a nutshell, I'm parameterizing the domain $D$ by the level sets of the function $g(x)$, rather than by the points in $D$ themselves. Shouldn't this be true?

If this isn't a MO-level question, then I apologize for spamming.

Comment by Joord Jacobsen

2011-10-21T17:26:35Z

An "arm" or a "branch" of a hyperbola in 2d -- edited the question statement to clarify.

Comment by Joord Jacobsen

2011-10-05T03:17:59Z

Thanks! Just what I was looking for.

Comment by Joord Jacobsen

2011-10-04T18:21:39Z

I clarified what I meant by "related" in the problem statement. Thanks.