Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:

"Keith F. Lynch" <kfl@KeithLynch.net> wrote:

...

With 216 billion sets, I get 0.356188363, even closer to that formula. That's the probability of a convex pentagon given five random points in a circle. The probability of a quadrilateral with one point in it is 0.548822606, and the probability of a triangle with two points in it is 0.094989031.

Suppose we pick five points in some region R (say, a circle). They form a convex pentagon _unless_ one of them lies within the triangle formed by three others. The expected number of times this happens is (5 choose 2) times the probability that a given point lies within a given triangle, which is 10 times the expected (area of triangle / area of R) so, calling that ratio f, the expected number of counterexamples to convexity is 10f.

.... So, finally, we need 1 - 10.35/48pi^2 + 10.3/32pi^2 which equals 1 - 1/48pi^2 (350 - 45) = 1 - 305/48pi^2 matching the value you found. (Phew.)

Thanks! What are the odds of a convex quadrilateral with one point in it, and the probability of a triangle with two points in it? They look like they might be 260/48pi^2 and 45/48pi^2 respectively (aka 65/12pi^2 and 15/16pi^2 respectively).

One could in principle do the same sort of calculations for any number of points, but they get messier. Also, the fact that we ended up with two (rational/pi^2) terms is kinda-coincidental; with six points we would need the expected _cube_ of (area(T)/area(R)), and if my calculations -- more honestly, my invocations of Mathematica's symbolic integration facilities -- are right then the expectation of area(T)^3 is 1001/(3200pi)

Interesting. It's a good thing I guessed right as to the form, given that Plouffe's Inverter and the Inverse Symbolic Calculator are down. Does anyone know of another website which, given a few digits of a real number, gives what the number might be?

and so we will start to get terms with pi^4 in the denominator as well as ones with pi^2 in the denominator. (Which will also make it trickier to guess the right answer purely by numerical experiment...)

Especially since the calculations get slower as the number of points go up. I've started working on six points. With three points, I get no crossings (of line segments joining the points), with four points I get either zero, representing a triangle with a point in it, or one, representing a quadrilateral, and with five points I get either 1, 3, or 5 crossings, representing a triangle containing 2 points, a convex quadrilateral containing 1 point, or a convex pentagon, respectively. So with six points I expected to get four possible numbers of crossings. Instead, I got eleven, from 3 to 15. I don't know what most of them mean. I looked up 1,2,3,11 in OEIS, and I get way too many hits. I guess I'll have to try 7 points, to get the next term. It could be a bug in my program, but I don't think so. I've confirmed that 3 is indeed the smallest number of crossings for K6. It's the "rectilinear crossing number," A014540. I'm surprised that there's no known formula for it, and that the solution for graphs as small as K28 are unknown. And I've confirmed that 15 is indeed the largest number of crossings for K6. I'm still trying to figure out the formula for that, given that I was mistaken when I assumed that, given a convex N-gon, every edge other than those on the perimeter, or those that share a vertex, crosses every other such edge. For the regular hexagon, some edges are parallel, and there are 15 crossings. I don't think the number can differ from 15 for an irregular (but still convex) hexagon, since (unless I'm confused) gradually transforming a regular hexagon into that irregular hexagon can't change the crossing number unless an edge passes through a vertex during the transformation, and there are no vertices in the interior for any edge to pass through. Perhaps I should attempt to find the rectilinear crossing number for K28 with my program. There will always be 3(n choose 4) pairs of edges to check for intersections. For n=28 that's 61425 pairs, which is not completely intractable.