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$
  • 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$ – John Hughes Nov 26 '17 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 Nov 26 '17 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$ – stuart stevenson Nov 26 '17 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$ – stuart stevenson Nov 28 '17 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 Nov 29 '17 at 2:46
7
$\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$
  • 1
    $\begingroup$ Can you evaluate the integral for me? $\endgroup$ – stuart stevenson Nov 29 '17 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$ – stuart stevenson Nov 29 '17 at 20:43
  • 1
    $\begingroup$ Perhaps find the expected are of the largest triangle formed from randomly placing 4 points? $\endgroup$ – stuart stevenson Nov 29 '17 at 20:54
  • 1
    $\begingroup$ appended amax distribution to answer $\endgroup$ – phdmba7of12 Nov 30 '17 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$ – stuart stevenson Nov 30 '17 at 19:50

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.