# The minimum-perimeter triangle of three sets of points

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\|)$$?

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

Here is some experimental data. The figure below shows $n{=}10$ random points in each of $X,Y,Z$, and the minimum perimeter $\triangle$:

$|X|=|Y|=|Z|=10$. Minimum (red-green-blue) perimeter $\triangle$ drawn.

Now here I let $n$ vary, with $|X|=|Y|=|Z|=n$, and average the results over $k$ trials:

The average min perimeter over $k{=}50$ random trials. Fit: $1.54 \,/\, n^{3/4}$.
The data fits Ori Gurel-Gurevich's calculation reasonably well.

• Will you test fits for a/n and a/n^(3/4) with no constant term? You seem to show f(50)/f(6) ~ (50/6)^(-0.8), which is close to the 3/4 from @OriGurelGurevich – Matt F. Sep 16 '17 at 8:39
• @MattF.: Good suggestion. The fit to $1/n^{3/4}$ is better than to $1/n$. – Joseph O'Rourke Sep 16 '17 at 13:25
• How about to $c/n^{1/2}$? – Aaron Meyerowitz Sep 17 '17 at 23:02
• @AaronMeyerowitz: Not nearly as good a fit to the same data. But I am just using least-squares, nothing sophisticated. And only up to $n{=}50$. – Joseph O'Rourke Sep 17 '17 at 23:07

Replacing the three samples by one sample $X$ we get the same answer up to constant factors (the probability that a given triangle has the three vertices in the three different samples is a constant). Then, the standard pigeonhole argument shows that the minimal circumcircle of a triangle has area of order $1/n$ (see R. E. Mills' paper for precise results), which indicates that the minimal perimeter is of order $1/\sqrt{n}.$

Miles, R.E., On the homogeneous planar Poisson point process, Math. Biosci. 6, 85-127 (1970). ZBL0196.19403.