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


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.

$\endgroup$
  • $\begingroup$ Thanks for the clarification. This should be well defined and can be calculated using an iterated integral. However, this particular choice of formalizing the problem might yield counterintuitive results. I would recommend taking a look at the paper ``A Lewis Carroll Pillow Problem: Probability of an Obtuse Triangle" by Stephen Portnoy. While it's not directly about the problem of MST, it shows how choosing different formalizations for problems can yield very strange results. $\endgroup$ – Gabe K Nov 17 '19 at 13:10
  • 1
    $\begingroup$ @GabeK Oh yes, probability is in the eye of the beholder. $\endgroup$ – Manfred Weis Nov 17 '19 at 13:53
3
$\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.

| cite | improve this answer | |
$\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 '19 at 15:26
  • $\begingroup$ What is MST? If I knew, maybe I can improve my answer? $\endgroup$ – Liviu Nicolaescu May 25 '19 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 '19 at 17:33
  • 2
    $\begingroup$ I would guess that the shape of the chosen domain would have an influence on that : what about uniformly chosen random point in a square ? In a triangle ? In a very long and thin rectangle ? $\endgroup$ – Benoît Kloeckner Nov 14 '19 at 16:01
  • $\begingroup$ Pick uniformly $n$ random points in a compact convex region $C$, and denote by $v_n$ the expected number of vertices of their convex hull. The behavior of $v_n$ as $n\to \infty$ depends on the regularity of the boundary. If the boundary of $C$ is smooth, then $v_n\sim const \cdot n^{1/3}$. If $C$ is a convex polygon, then $v_n\sim const \cdot\log n$. The constants in the above asymptotic expansions depend explicitly on the geometry of the boundary of $C$. The situation when $C$ is a thin rectangle can be reduced to the case $C$ is a square via an area preserving linear map. $\endgroup$ – Liviu Nicolaescu Nov 14 '19 at 16:31
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.