The minimum-perimeter triangle of three sets of points

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.