1
$\begingroup$

Question:

Consider a fixed number $k > 3$ of random points in the plane, each independently distributed according to a 2D standard normal distribution. What is the probability that the convex hull of these $k$ points is a triangle?

Presumably there is no closed form formula (or is there?), so I would also be interested in some sort of bounds on this probability.

Motivation:

I have coded the following (lazy) way to generate random quadrilaterals in the plane:

  1. Pick $k=10$ points from a 2D standard normal distribution

  2. Extract 4 points from the boundary of the convex hull of those 10 points

This is convenient since there is a simple and fast 1-liner in my programming language to do step 2 (convhull command in Matlab). It would be nice to know how likely it is that this algorithm will fail, and/or how large I need to make $k$ so that I can be reasonably certain it will "never" fail.

$\endgroup$
  • 2
    $\begingroup$ The case $k=4$ is treated by Christian Blatter in these notes. I have some ideas about $k\gt4$ but probably won't come around to write them down for a while. $\endgroup$ – joriki Jul 5 '16 at 10:37
  • $\begingroup$ Why not an even lazier algorithm? (1) Generate 4 random points (2) Done. If you need convex quadrilaterals, then repeat step (1) if the convex hull contains only three points. $\endgroup$ – Mark H Jul 5 '16 at 10:39
  • $\begingroup$ @Mark H I have tried this. For reasons of pipelining efficiency and code vectorization when generating large numbers of quadrilaterals, it seems to be much faster to just generate extra points to begin with, thereby avoiding using loops and conditional statements. Also, now I am interested in the problem just out of curiosity. $\endgroup$ – Nick Alger Jul 5 '16 at 20:09
  • 1
    $\begingroup$ @joriki Thanks! These notes are great. $\endgroup$ – Nick Alger Jul 5 '16 at 20:13
1
$\begingroup$

Some numerical results (C++ code here). For each number of points, 10,000,000 sets of points were generated with a 2D normal distribution centered at the origin with a standard deviation of 1. The convex hull was found for each set and counted if the convex hull was a triangle.

It looks like for 17 points or more the probability is about 1 in 10,000,000 or less.

Number       Probability of
of Points    triangle convex hull
3            1
4            0.3512278
5            0.1352262
6            0.0520421
7            0.0194204
8            0.0070548
9            0.002416
10           0.0008214
11           0.0002637
12           8.3e-05
13           2.51e-05
14           7.6e-06
15           1.3e-06
16           1e-06
17           0
18           1e-07
19           0
20           0

Update

Results from a run with 100,000,000 samples per number of points.

Number       Probability of
of Points    triangle convex hull
3            1
4            0.35095143
5            0.13514043
6            0.05205319
7            0.01946472
8            0.00701896
9            0.00244124
10           0.00081369
11           0.00026413
12           8.177e-05
13           2.477e-05
14           7.1e-06
15           1.98e-06
16           5.1e-07
17           1.4e-07
18           0
19           3e-08
20           0
$\endgroup$
  • $\begingroup$ In case anyone was wondering, $k=3$ is mostly a sanity check (of my code, not me (no hope in that department)). $\endgroup$ – Mark H Jul 6 '16 at 9:12

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.