8
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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


          XYZ
          $|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:


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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Matt F. Sep 16 '17 at 8:39
  • 1
    $\begingroup$ @MattF.: Good suggestion. The fit to $1/n^{3/4}$ is better than to $1/n$. $\endgroup$ – Joseph O'Rourke Sep 16 '17 at 13:25
  • $\begingroup$ How about to $c/n^{1/2}$? $\endgroup$ – Aaron Meyerowitz Sep 17 '17 at 23:02
  • $\begingroup$ @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$. $\endgroup$ – Joseph O'Rourke Sep 17 '17 at 23:07
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.