2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ maybe I missed something, but where is the conditional probability calculated, that the MST of 4 points in convex configuration has 3 leaf nodes or, that the MST of 4 points in deltoid configuration has two leaf nodes? $\endgroup$ – Manfred Weis May 25 at 15:26
  • $\begingroup$ What is MST? If I knew, maybe I can improve my answer? $\endgroup$ – Liviu Nicolaescu May 25 at 16:03
  • $\begingroup$ Sorry for not mentioning that: the MST is the Minimum Spanning Tree, i.e. in the case of 4 aoints a set of 3 distinct connections between pairs of points such that the connections don't constitute to a triangle and, that their length-sum is minimal under that condition. $\endgroup$ – Manfred Weis May 25 at 17:33

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.