Probabilities of four points being in convex/deltoid configurations

Question

Question:

what is the probability that four distinct points in general position in the Euclidean plane are in convex configuration, depending on the number of leaf nodes in their Minimum Spanning Tree (MST)?

Put differently, what are the probabilities for the following situations:

• the points are in convex configuration and
  • the MST has two leaf nodes?
  • the MST has three leaf nodes?
• the points are in deltoid configuration
  • the MST has two leaf nodes?
  • the MST has three leaf nodes?

I assume that a quadruplet of points has a higher probability of being in convex configuration if its MST has two leaf nodes than if it has three, but that that probability is less than 1.

Addendum:

In reply to @GabeK's request for a definition of the sampling space, I would suggest the following, which deviates from what is the basis of answers to Sylvester's Four Point problem.

Instead of sampling the four points uniformly from planar geometric shape, whose set of inner points is path-connected, I request that the smallest closed disk that contains the four points is the unit disk and, that the sequence $(A,B,C,D)$ of points returned by the sampling process has the property, that $\lbrace A,B\rbrace$ defines one of the most distant pair of points and that the circum circle of $\lbrace A,B,C\rbrace$ isn't larger than the one of $\lbrace A,B,D\rbrace$.

The motivation for those restrictions on the sampling process is as follows:

• the probability of four points being in convex configuration should be independent of the order in which they are sampled
• the probabilites should be independent of similarity-preserving transformations of the Eulidean plane; i.e. if we calculate the probability that the points are in convex configuration before and after they have been subjected to such a transformation, both values should be the same because those transformations preserve convexity.
• we can always find a similarity-transformation, that takes the smallest enclosing circle of a quadruplet of points to the boundary of the unit disk.

All in all every quadruplet of points, whose smallest enclosing circle is the unit circle, represents transfinitely quadruplets of points that have been sampled from the entire Euclidean plane and have the same convexity predicate.

Answer 1

First, since the problem is obviously rescale and rotationally invariant we can assume that the four points are chosen uniformly at random inside the unit disk $\newcommand{\bD}{\mathbb{D}}$ $\bD$. Denote by $V$ the number of points vertices of the convex hull of these four random points. Note that $V$ is a random variable and $V\in\{3, 4\}$ almost surely. $\newcommand{\bE}{\mathbb{E}}$ $\newcommand{\bP}{\mathbb{P}}$ We set $$ p:=\bP[V=4]. $$ Note that $\bP[V=3]=1-p$ so the expectation $\bar{v}$ of $V$ is $$ \bar{v}= 3(1-p)+4p=3+p, $$ so $$ p=\bar{v}-3. $$ The computation of $\bar{v}$ is a special case of the Renyi-Sulanke problem.

Denote by $P_1,P_2,P_3,P_4$ the $4$ random points and by $p_{12}$ the probability that the points $P_3,P_4$ lie on the same side of the line determined by $P_1,P_2$. Then, as shown by Renyi and Sulanke we have $$ \bar{v}=\binom{4}{2}p_{12}= 6p_{12}. $$ Given two points $P,Q$ we denote by $L(P,Q)$ the line determined by $P,Q$ and by $a(P,Q)$ the area of the part of the disk that lies on the same side of $L(P,Q)$ as the center of the disk. Set $$ \bar{a}(P,Q)=\frac{1}{\pi} a(P,Q). $$ Then $$ p_{12}= \frac{1}{\pi^2}\int_{\bD^2}\Big(\; \bar{a}(P,Q)^2+(1-\bar{a}(P,Q))^2\;\Big)dPdQ $$ $$=\int_{\bD^2}\Big(\; 2\bar{a}(P,Q)^2-2\bar{a}(P,Q)+1\;\Big) dPdQ $$ $$ =1-2\int_{\bD^2} \bar{a}(P,Q)\big(\; 1-\bar{a}(P,Q)\;\big) dPdQ. $$ The line $L(P,Q)$ has a unique equation of the form $$ x\cos \theta+y\sin\theta =p,\;\;p\in[0,1], \;\;\theta\in[0,2\pi]. $$ We denote by $L_{\theta,p}$ the line described by such an equation. The chord cout-ut by the disk on this line has length $$\ell(p)=2\sqrt{1-p^2}.$$ For such a line we have $$ a(P,Q)=\frac{\pi}{2}+2\int_0^p \sqrt{1-x^2} dx =\frac{\pi}{2} +p\sqrt{1-p^2} +\arcsin(p). $$ We set $$ \alpha(p):=\frac{1}{2}+ \frac{1}{\pi} \big(\; p\sqrt{1-p^2} +\arcsin(p)\;\big)=\bar{a}(P,Q). $$ As explained in the equality (5) in here we have $$ \int_{\bD^2} \bar{a}(P,Q)\big(\; 1-\bar{a}(P,Q)\;\big) dPdQ $$ $$ =\frac{1}{3}\int_0^{2\pi} \int_0^1\alpha(p)(1-\alpha(p)) \ell(p)^3 dp d\theta, $$ $$ =\frac{2\pi}{3} \int_0^1 \alpha(p)(1-\alpha(p)) \ell(p)^3 dp. $$ This integral can be computed/approximated using a computer algebra system such as MAPLE or MATHEMATICA.

Answer 2

This is not an answer, but was too long to be a comment. The answer will depend on the probability distribution that the points are drawn from. In particular, without even considering the minimum spanning tree, the probability that the points are in convex configuration versus ``deltoid configuration" appears to be a restatement of Sylvester's four-point problem, which calculates the probability that four points drawn uniformly at random have a quadrilateral as their convex hull. For this question, the way that points are drawn changes the probability. For instance, the probability of a convex configuration is $1− \frac{35}{12 \pi^2} \approx .70448$ if the points are drawn uniformly from an ellipse, $2/3$ if the points are drawn from a triangle, and $\frac{6 \arcsin(1/3)}{\pi} \approx .64904 $ if the points are drawn from a two-dimensional normal distribution. As such, to answer your question about minimum spanning trees, we also need some information on how the points are drawn.