# Answered: With what probability do $4$ points placed uniformly randomly in the unit square of $\mathbb{R}^2$ form a convex/concave quadrilateral?

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.

• 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. – John Hughes Nov 26 '17 at 2:13
• 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. – user202729 Nov 26 '17 at 2:48
• 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. – stuart stevenson Nov 26 '17 at 20:54
• 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. – stuart stevenson Nov 28 '17 at 21:51
• "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$. – Paul Nov 29 '17 at 2:46

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.

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!

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

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% • Can you evaluate the integral for me? – stuart stevenson Nov 29 '17 at 15:29 • 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. – stuart stevenson Nov 29 '17 at 20:43
• Perhaps find the expected are of the largest triangle formed from randomly placing 4 points? – stuart stevenson Nov 29 '17 at 20:54
• appended amax distribution to answer – phdmba7of12 Nov 30 '17 at 19:36
• 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. – stuart stevenson Nov 30 '17 at 19:50