On 22/07/2020 03:18, Keith F. Lynch wrote:
How would one go about enumerating all arrangements?
This looks relevant: http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/orderty...
Thanks. But that apparently just points to abstracts of papers that aren't online, and binary data files in undocumented formats.
The "theory" link goes to a list of papers that are all online there on the site -- all those ".ps.gz" links.
I re-ran my program on two billion arrangements of seven points, and counted the RCNs of each. This time, I discarded any arrangements that contained any vertical line. Earlier I had just not worried about the resulting divide-by-zero errors, as those would cause errors only in the ninth digit or later. I also checked for the other possible source of division by zero, parallel lines, but as always those never happened. I did not check for three points in a line. Anyhow, I got surprising results. There are no longer just 13 possible RCNs for n=7, there are 24:
9: 2854081 10: 1 11: 11027816 12: 1 13: 23633438 14: 6 15: 57311057 16: 2 17: 146814179 18: 4 19: 239174223 20: 6 21: 275889258 22: 4 23: 384422525 24: 1 25: 309111456 26: 2 27: 205481998 28: 2 29: 180328085 30: 1 31: 116777008 35: 47174846
I'm not sure this isn't a bug. Can someone come up with a proof that there can't be any even-numbered RCN for 7 points? Or that there can be?
For a convex 7-gon we have (7 choose 4) = 35 crossings. (Counting by multiplicity, if any crossings coincide.) When you move the points around, the number of crossings only changes when a point crosses a line. When this happens, 7-1=6 crossings appear or disappear, one for each other point. So the parity of the number of crossings, when no three points are collinear, is always the same as that of (7 choose 4). In general, when n is odd, the parity will always be the same as that of (n choose 4). That is: even when n is 0,1,2,3 mod 8 and odd when n is 4,5,6,7 mod 8. For even n, this argument doesn't lead to any restriction. I think your isolated 1s and 2s and so forth are occurring when you have points collinear or nearly enough collinear that numerical errors can produce inconsistent results. I suggest checking for collinearity and ignoring configurations where any three points are "too close" to collinear. -- g