Worst-case nearest-neighbor distances between regions

Question

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.

Answer 1

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

Answer 2

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