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.



Worst-case nearest-neighbor distances between regions
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). 


