Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose that $S_1,\dots,S_n$ is a collection of disjoint shapes in the plane, and let $\mathcal{X}$ denote the set of all $n$-tuples of points $\lbrace x_1,\dots,x_n\rbrace$ such that $x_i\in S_i$ for each $i$. For any such tuple $X = \lbrace x_1,\dots,x_n\rbrace$, let $F(X)$ be defined as

$F(X) = \max_{i} \min_{j\neq i} \|x_i - x_j\| $,

i.e. the maximum nearest-neighbor distance between the points $x_i$. Is there a lower bound for the quantity $\max_{X \in \mathcal{X}} F(X)$? Put another way, I'd like to find the tightest possible value of $r$ in the following statement:

"Suppose that $S_1,\dots,S_n$ is a collection of disjoint shapes in the plane. Then there exists an $n$-tuple of points $\lbrace x_1,\dots,x_n\rbrace$ such that $x_i \in S_i$ for each $i$ and an index $i^*$ such that $ \| x_{i^*} - x_j \| \geq r $ for all indices $j\neq i^*$."

I am conjecturing that the answer is inversely proportional to $\sqrt{n}$ and proportional to the square root of the total area of the regions.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

If $p \in S_i$ is not a possible $x_{i^*}$ for a given $r$, there must be some $j$ such that $S_j$ is contained in the disk of radius $r$ around $p$. In particular a possible $r$ is half the second-largest diameter of the $S_i$'s. And this is within some constant factor of optimality, if you consider a case where $S_1, \ldots, S_{n-1}$ are disks and $S_n$ is a line segment (or a thin rectangle).

share|improve this answer

I assume you are seeking a lower bound for $r$ for configurations of a fixed total area $A$, otherwise it just does not make sense.

Yes the bound is $\sim C\sqrt{A/n}$ for some constant $C>0$ but I don't know what is the exact value of $t$.

Indeed, $r=\sqrt{A/\pi n}$ always works. Indeed, pick arbitrary points $x_i\in S_i$ and consider balls $B_i$ of radius $r$ centered at $x_i$. The sum of areas of $B_i$ equals $A$, hence they do not cover the union $\bigcup S_i$ (or they are disjoint, in which case the points $x_i$ are a good configuration). So there is a point $x$ in some $S_{i^*}$ not covered by these balls. Move $x_{i^*}$ to this point and you are done.

On the other hand, there are collections $\{S_i\}$ such that $r=\sqrt{2A/\pi n}$ does not work. Indeed, consider the following configuration for even $n$: for each $j\le n/2$, $S_{2j-1}$ is a single point and $S_{2j}$ is the open ball centered at this point, with the center removed. The centers are chosen far away from one another so that the sets are disjoint. Clearly for any choice $x_i\in S_i$, we have $|x_{2j}-x_{2j-1}|<r$, and the total area equals $A$.

To see that there is a specific limit constant $C$, let $A_n$ denote the supremum of total areas of $n$ sets such that $F(X)\le 1$ for any selection $X=\{x_i\}$, $x_i\in S_i$. It is easy to see that the sequence $A_n$ is subadditive: $A_{m+n}\le A_m+A_n$. Indeed, an example with $m+n$ can be contracted as the union of examples with $m$ and $n$ sets (translated far away from each other so that they become disjoint). Hence there is a limit $A_\infty = \lim A_n/n$ and then $C=1/\sqrt{A_\infty}$.

share|improve this answer

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.