If $X$ and $Y$ are two sets of $n$ independent, uniformly sampled points in the unit square, then standard methods can show that the expected minimum distance between points in $X$ and $Y$ is proportional to $1/n$, that is, $$E(\min\_{i,j}\|x\_i - y\_j \|)\sim 1/n$$as $n\to\infty$. Is there anything similar that can be said when we have three sets of points $X,Y,Z$, and we look for the triangle whose perimeter is shortest? I.e., $$E(\min\_{i,j,k}\|x\_i-y\_j\|+\|y\_j-z\_k\| + \|z\_k - x\_i\|)$$?



The minimum-perimeter triangle of three sets of points
Partition the unit square into small squares of area roughly $a$. Your question is equivalent to asking for which $a$ do we typically see about 1 small square with points from each of $X$,$Y$ and $Z$? this probability is roughly $(an)^3$ since the probability of seeing a point from each set is about $an$ and they're independent. There are $1/a$ small squares so the expected number of squares with points from each set is roughly $(an)^3/a=a^2n^3$. So if we want this to be roughly 1 we need to set $a=n^{-3/2}$. The diameter of a small square is therefore $n^{-3/4}$.


Generalizing for $k$ different sets and dimension $d$ yields $n^{-\frac{k}{d(k-1)}}$.


