22
$\begingroup$

I have this problem that I've struggled with for a while. If you place $4$ points randomly into a unit square (uniform distribution in both $x$ and $y$), with what probability will this shape be convex if the $4$ points are connected in some order? Equivalently, with what probability will there be a point inside the triangle with the largest area with vertices at the other $3$ points.

In particular I am interested in the answer for when this area of support is $\mathbb{R}^2$ and is uniform.

I ran a simulation and found that on a unit square the answer is about $71\%$ concave. On a unit circle picking polar co-ordinates r and theta from uniform random distributions results in a a probability of concavity of $68\%$. When the distribution for r is altered so that each point in the circle is equally likely then this falls to $51\%$.

Any advice or links for a possible answer or whether this is even possible would be appreciated.

EDIT: It turns out this problem is the same as Sylvester's 4 point problem. Alas I am 150 years too late. Thanks to all who helped. Only one person gave an answer, not quite correct but I award the bounty to them anyway for their efforts.

$\endgroup$
22
  • 2
    $\begingroup$ I'm not sure that your "equivalently" is really an equivalent probability, Perhaps the right question is "what's the probability that the convex hull is a quadrilateral?" The number 71% makes me think of $\frac{\sqrt{2}}{2}$; the last case (uniform points on a disk) giving 51% sure makes me think it's 0.5. $\endgroup$ Commented Nov 26, 2017 at 2:13
  • 1
    $\begingroup$ This is pretty equivalent to "what is the expected triangle area formed by 3 uniformly random point inside a unit square". I can't think how to integrate an absolute value (Abs[(ax - bx) (ay - cy) - (ax - cx) (ay - by)]/2), though. $\endgroup$
    – user202729
    Commented Nov 26, 2017 at 2:48
  • 2
    $\begingroup$ The thing about calculating the area from 3 points is that the 4th point can either be inside that triangle, outside that triangle making a convex quadrilateral or outside that triangle forming a concave quadrilateral so it's not really about the are per se. $\endgroup$ Commented Nov 26, 2017 at 20:54
  • 1
    $\begingroup$ I have found a partial solution here. It turns out the unit circle case is called Sylvester's 4 point problem. The values in the link confirm my simulation. The puzzle is still open for the infinite plane problem but perhaps this helps. $\endgroup$ Commented Nov 28, 2017 at 21:51
  • 4
    $\begingroup$ "In particular I am interested in the answer for when this area of support is $\mathbb{R}^2$ and is uniform" - What do you mean? There is no uniform distribution on $\mathbb{R}^2$. $\endgroup$
    – Paul
    Commented Nov 29, 2017 at 2:46

2 Answers 2

9
$\begingroup$

Here is a different approach to the problem. Consider a random triangle illustrated below. Regions are labelled near ($N_i$) and far ($F_i$) from point $i$. $T$ is the triangle. random triange illustrating random regions in the unit square

If the 4th point falls in regions $F_1$, $F_2$, or $F_3$ a convex quadrilateral will result. The probability that 4 points produce a convex shape is equivalent to the probability that the 4th point will be in one of those regions. That is, $p=E[F_1+F_2+F_3]$ where $F_i$ is the random variable expressing the area of that region.

To simplify the calculations, consider the shaded region labelled $A_1$ and the counterparts $A_2$ and $A_3$. $$F_1+N_2+N_3=A_1$$ $$N_1+F_2+F_3+T=1-A_1$$ Combining these one finds, $$F_1+F_2+F_3 = 2 - 2T - A_1 - A_2 - A_3$$ and therefore, $$p=E[F_1+F_2+F_3]=2 - 2E[T] - 3E[A]$$ Fortunately others have worked out $E[T]={11\over144}$

To work out $E[A]$, I considered separately the case where the unit square is bisected across opposite sides (as is the case for $A_1$). You can show that this occurs with probability ${2\over3}$, given two uniform random points. The smallest of the two areas $A_\min$ follows the distribution $$f(a_\min)=4a_\min$$ for $0<a_\min<{1\over2}$. Given the two points $(2,3)$ point $1$ point will fall in the smaller of the two areas with probability $a_\min$, in which case $A_1=1-a_\min$. $$ E[A_{opp}]=16\int_0^{1\over2}a_\min^2(1-a_\min)\,da_\min = {5\over12} $$

For the case where the unit square is cut across a corner (as is the case for $A_2$), $A_\min={1\over2}X_0Y_0$ where $X_0$ and $Y_0$ are independent random variables with the identical distribution, $f(x)=2x$ for $0<x<1$. This gives the distribution for $A_\min$, $$f(a_\min)=-16 a_\min \log 2a_\min$$ for $0<a_\min<{1\over2}$. $$ E[A_{corner}]=-32\int_0^{1\over2}a_\min^2(1-a_\min)\log 2a_\min\,da_\min = {23\over72} $$ And so, overall $$E[A] = P(A_{opp})E[A_{opp}]+P(A_{corner})E[A_{corner}]={2\over3}{5\over12}+{1\over3}{23\over72} = {83\over216}$$ Finally, $$ p = 2 - 2{11\over144} - 3{83\over216}={25\over36}=\left({5\over6}\right)^2=0.69\bar{4} $$ which is close to your simulation result. A very simple form!

$\endgroup$
2
+100
$\begingroup$

$P_{convex}=\int_0^1 da a_{123}p(a_{123})$ where $a_{123}=\frac{1}{2}\left|(\mathbf{x}_{12} \times \mathbf{x}_{13})\right|$ this is the probability that the 4th point falls within the triangle formed by the first three. Normalization included due to unit square, and $$p(a)=\frac{1}{2} \int_0^1 dx_1 \int_0^1 dx_2 \int_0^1 dx_3 \int_0^1 dy_1 \int_0^1 dy_2 \int_0^1 dy_3 \delta \left( a - \sqrt{\left( (x_2 - x_1)^2 (y_3 - y_1)^2 + (y_2 - y_1)^2 (x_3 - x_1)^2 \right) } \right)$$

an integral which might be difficult to evaluate in closed form, where $\delta(x)$ is the Dirac delta function.

The $p(a)$ probability density function for the area of the triangle formed by three uniformly random points in the unit square seems to fit quite well to the beta distribution with $\alpha = 1.18$ and $\beta = 5.1$ and an upper bound of $\frac{1}{2}$

The percentage of fourth points that fall inside the triangle formed by first three is then the expectation of the area $E\left[a\right]=\frac{\alpha / 2}{\alpha+\beta}$ or ~10%, corresponding to concave fraction of 90%. Seems off ...

enter image description here

Also looked at the distribution of the maximum area of the 4 triangles formed by a set of 4 points each picked from $(U[0,1],U[0,1]) Mean moves from 9% to 15%

enter image description here

$\endgroup$
6
  • 1
    $\begingroup$ Can you evaluate the integral for me? $\endgroup$ Commented Nov 29, 2017 at 15:29
  • 2
    $\begingroup$ I appreciate your effort. I think what you have is an approximation to Sylvester's 4 point problem which has a probability of $\frac{11}{144}$. Then considering that I don't mind which point is not part of the convex hull, we multiply by 4 for the 4 possible points on the inside. Unfortunately, this is not the answer to the question as there are additional spaces outside the triangle formed by the first 3 points that would also give a convex hull with 3 points. A good effort and the current front runner for the bounty as we now know that $\frac{11}{36}$ is a lower bound. $\endgroup$ Commented Nov 29, 2017 at 20:43
  • 1
    $\begingroup$ Perhaps find the expected are of the largest triangle formed from randomly placing 4 points? $\endgroup$ Commented Nov 29, 2017 at 20:54
  • 1
    $\begingroup$ appended amax distribution to answer $\endgroup$ Commented Nov 30, 2017 at 19:36
  • 1
    $\begingroup$ Looks good. I think if you multiply that by 4 then you get Sylvester's 4 point problem solution discussed above. Thanks for your help. $\endgroup$ Commented Nov 30, 2017 at 19:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .