On 16/07/2020 02:40, Keith F. Lynch wrote: [me:]
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.)
[Keith:]
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).
Well, we found that (writing f=25/48pi^2 and f2=3/32pi^2) E(number of point-in-triangle cases) = 10f E(number of two-points-in-triangle cases) = 10f2 and the second of those should be exactly the probability of getting a triangle with two points in it, so that's 30/32pi^2 which equals your 15/16pi^2 or 45/48pi^2. And then the probability of getting a convex quadrilateral with one point in is 1 - Pr(convex pentagon) - Pr(tri+2pts) or 1 - (1-305/48pi^2) - 45/48pi^2 = 260/48pi^2 = 65/12pi^2. So your numbers are right.
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.
The maximum number of intersections is always (n choose 4). If you pick any four of the vertices, there's just one interior intersection formed by edges between them. (The number of _distinct points_ they produce can be less when more than two edges meet at a point. There's a paper at http://www-math.mit.edu/~poonen/papers/ngon.pdf that purports to find the rather horrible formula for that in the case where the polygon is regular.) I don't have much intuition for which of the numbers in [rectilinear crossing number, (n choose 4)] are actually attainable. Unless the pattern is very simple, I suspect it's going to be pretty tough to count them. -- g