Eight points are selected at random from the interior of a unit circle.
What is the probability that these eight points constitute the eight vertices of a convex octagon?
For purposes of testing whether the condition is true in each simulation trial, it seems the best way is to find the vector angle from each point to each other point. If each of the eight points has some gap in the ordered array of vector angles that exceeds 180°, then the eight points form a convex octahedron. The converse is obviously true, so it's an if-and-only-if condition (both necessary and sufficient) so long as my first statement is correct, and I think it is.
DefDbl A-Z
Dim crlf$, x(8), y(8), direction(8, 8), raddeg, dir(8), no(8)
Private Sub Command1_Click()
Form_Load
End Sub
Private Sub Form_Load()
Form1.Visible = True
Randomize Timer
'Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
raddeg = 45 / Atn(1)
For tr = 1 To 10000
For pt = 1 To 8
Do
xp = 2 * Rnd(1) - 1
yp = 2 * Rnd(1) - 1
Loop Until xp * xp + yp * yp < 1
x(pt) = xp: y(pt) = yp
Next
For pt = 1 To 8
x0 = x(pt): y0 = y(pt)
For i = 1 To 8
If i <> pt Then
xp = x(i): yp = y(i)
xdiff = xp - x0: ydiff = yp - y0
angle = atan(ydiff / xdiff)
If xdiff < 0 Then angle = angle + 180
If angle < 0 Then angle = angle + 360
If angle > 360 Then angle = angle - 360
direction(pt, i) = angle
direction(i, pt) = angle - 180
If direction(i, pt) < 0 Then direction(i, pt) = direction(i, pt) + 360
If direction(i, pt) > 360 Or direction(i, pt) = 0 Or direction(pt, i) > 360 Or direction(pt, i) = 0 Then
xxx = xxx
End If
End If
Next
Next pt
hit = 1
For pt = 1 To 8
For i = 1 To 8
dir(i) = direction(pt, i)
If dir(i) = 0 Then
xxx = xxx
End If
Next
Do
done = 1
For i = 1 To 7
If dir(i + 1) < dir(i) Then
h = dir(i)
dir(i) = dir(i + 1)
dir(i + 1) = h
done = 0
End If
Next
Loop Until done
found = 0
For i = 2 To 7
If dir(i + 1) - dir(i) >= 180 Then
found = 1: Exit For
End If
Next
If dir(2) - dir(8) + 360 >= 180 Then found = 1
If found = 0 Then
hit = 0: Exit For
End If
Next
If hit Then
hitct = hitct + 1
If hitct > 30000 Then
For pnt = 1 To 8
Text1.Text = Text1.Text & mform(x(pnt), "#0.0000") & mform(y(pnt), "#0.0000") & " "
For i = 1 To 8
dir(i) = direction(pnt, i)
no(i) = i
Next
Do
done = 1
For i = 1 To 7
If dir(i + 1) < dir(i) Then
h = dir(i): h2 = no(i)
dir(i) = dir(i + 1): no(i) = no(i + 1)
dir(i + 1) = h: no(i + 1) = h2
done = 0
End If
Next
Loop Until done
For i = 2 To 8
Text1.Text = Text1.Text & Str(no(i)) & mform(dir(i), " ###0.0") & " "
Next
Text1.Text = Text1.Text & crlf
Next
Text1.Text = Text1.Text & crlf
End If
End If
trct = trct + 1
Next tr
Text1.Text = Text1.Text & crlf & hitct & Str(trct) & Str(hitct / trct) & " done"
End Sub
Function atan(x)
atan = raddeg * Atn(x)
End Function
Function mform$(x, t$)
a$ = Format$(x, t$)
If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
mform$ = a$
End Function
The coding of "hitct > 30000" is the equivalent of commenting out that set of code. For one run it was given as hitct < 3, to get details on two sample hits (seen at the bottom, below).
hits trials fraction
100 10000 .01 done
92 10000 .0092 done
88 10000 .0088 done
86 10000 .0086 done
81 10000 .0081 done
78 10000 .0078 done
91 10000 .0091 done
66 10000 .0066 done
87 10000 .0087 done
83 10000 .0083 done
95 10000 .0095 done
99 10000 .0099 done
79 10000 .0079 done
89 10000 .0089 done
98 10000 .0098 done
82 10000 .0082 done
87 10000 .0087 done
83 10000 .0083 done
88 10000 .0088 done
89 10000 .0089 done
94 10000 .0094 done
103 10000 .0103 done
91 10000 .0091 done
79 10000 .0079 done
91 10000 .0091 done
82 10000 .0082 done
78 10000 .0078 done
81 10000 .0081 done
90 10000 .009 done
90 10000 .009 done
97 10000 .0097 done
99 10000 .0099 done
112 10000 .0112 done
95 10000 .0095 done
71 10000 .0071 done
79 10000 .0079 done
83 10000 .0083 done
91 10000 .0091 done
97 10000 .0097 done
91 10000 .0091 done
88 10000 .0088 done
83 10000 .0083 done
74 10000 .0074 done
95 10000 .0095 done
93 10000 .0093 done
60 10000 .006 done
96 10000 .0096 done
82 10000 .0082 done
That's 48 rows for 480,000 trials, with 48 reseedings of the random number generator with new seeds based on the time of hitting the command button.
Excel tells me the total hits is 4206. 4206/480000 = .0087625, so it seems the probability is less than 1% (about 0.88%) or about 1 in 114.
Two sample successful hits are shown below. In each case the x and y coordinates of each of the eight points are shown. To the right of each such pair are the vector angles to the other points in ascending order, each preceded by the number (printout line) of the other point, so in the first set, the angle from the first point to the seventh point is 165.7. The angle from the first point to the fifth is 291.2 and this is in fact the larger than 180° angle for point 1: pt5-pt1-pt7. All angles are measured counterclockwise, so no internal angles are considered. These verify as convex octahedra.
0.5759 0.3652 7 165.7 6 206.6 4 219.1 3 232.1 2 240.6 8 257.9 5 291.2
-0.1620-0.9422 8 29.5 5 35.0 1 60.6 7 92.4 6 118.3 4 148.9 3 159.5
-0.3791-0.8608 8 16.1 5 26.8 1 52.1 7 83.8 6 105.4 4 142.1 2 339.5
-0.6629-0.6402 5 14.6 1 39.1 7 70.1 6 76.7 3 322.1 2 328.9 8 359.6
0.8171-0.2557 1 111.2 7 141.6 6 177.9 4 194.6 3 206.8 2 215.0 8 220.6
-0.5599-0.2045 1 26.6 7 66.5 4 256.7 3 285.4 2 298.3 8 334.3 5 357.9
-0.2241 0.5696 6 246.5 4 250.1 3 263.8 2 272.4 8 295.6 5 321.6 1 345.7
0.3594-0.6474 5 40.6 1 77.9 7 115.6 6 154.3 4 179.6 3 196.1 2 209.5
0.0832-0.7422 2 75.8 7 80.6 3 86.9 5 97.8 6 129.1 8 145.5 4 149.6
0.2145-0.2217 7 84.6 3 93.5 5 112.7 6 161.8 8 188.4 4 197.1 1 255.8
0.1598 0.6710 5 215.3 6 222.5 8 235.9 4 240.8 1 266.9 2 273.5 7 295.2
-0.4545-0.4273 2 17.1 7 49.4 3 60.8 5 68.3 6 101.1 8 122.7 1 329.6
-0.0860 0.4969 3 35.3 6 225.7 8 242.5 4 248.3 1 277.8 2 292.7 7 348.6
-0.5433 0.0275 7 25.8 3 42.5 5 45.7 8 274.2 4 281.1 1 309.1 2 341.8
0.2758 0.4241 3 115.2 5 168.6 6 205.8 8 223.6 4 229.4 1 260.6 2 264.6
-0.5171-0.3298 2 8.4 7 43.6 3 55.9 5 62.5 6 94.2 4 302.7 1 325.5
Edited on August 24, 2016, 6:31 pm
|
|
Posted by Charlie
on 2016-08-24 18:30:39 |
simulation
