Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
The "theory" link goes to a list of papers that are all online there on the site -- all those ".ps.gz" links.
Thanks. Apparently, if I understand correctly, the key insight is that every triangle, i.e. subset of three of the n vertices, is either clockwise or counterclockwise when drawn in order of the vertex numbers, and that the RCN, number of edges in the convex hull, and everything else relevant is uniquely determined by that n-choose-3 bit number. Of course it has to be such that none of the properties change under any of the n! possible renumberings of the vertices. (Or under reflection, but that's the same as reversing the order of the numbers.) I came close, in that I was thinking about keeping track of the number of vertices interior to each such triangle. But I also had a lot of unrelated ideas, such as treating the edges as unit resistors, or perhaps as resistors whose resistance equaled their lengths, and computing the in-circuit resistances between each pair of vertices.
I re-ran my program on two billion arrangements of seven points, and counted the RCNs of each. ... Anyhow, I got surprising results. ....
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?
Thanks for the proof that there can't be.
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.
I did notice that the smallest and largest RCNs were always of the same, vastly more common, parity for every odd n-gon, and I did notice the mod 8 pattern.
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 thought that might be the case, but I also thought that such collinearity should be far too rare to account for my results. And I was right about the latter. I just ran it again, keeping track of slopes and other things, and no two edges were anywhere close to having the same slope. (Three vertices on the same line would cause three edges to have the same slope, the three edges of a degenerate triangle.) Just 21 of the 2 billion sets of 7 points had an even RCN. Here's one of them: The (31-bit positive integer) coordinates of the 7 vertices: 0: x=1656517416, y=413766638 1: x=156845284, y=289993739 2: x=912742874, y=1050551595 3: x=1121769010, y=1049033428 4: x=1512620013, y=1049033428 5: x=996250662, y=1587493622 6: x=1715909114, y=2007618816 The slopes of the 21 edges. Note that they're all quite different: 0,1: dx=-1499672132, dy=-123772899, dy/dx=0.082533 0,2: dx=-743774542, dy=636784957, dy/dx=-0.856153 0,3: dx=-534748406, dy=635266790, dy/dx=-1.187973 0,4: dx=-143897403, dy=635266790, dy/dx=-4.414720 0,5: dx=-660266754, dy=1173726984, dy/dx=-1.777656 0,6: dx=59391698, dy=1593852178, dy/dx=26.836279 1,2: dx=755897590, dy=760557856, dy/dx=1.006165 1,3: dx=964923726, dy=759039689, dy/dx=0.786632 1,4: dx=1355774729, dy=759039689, dy/dx=0.559857 1,5: dx=839405378, dy=1297499883, dy/dx=1.545737 1,6: dx=1559063830, dy=1717625077, dy/dx=1.101703 2,3: dx=209026136, dy=-1518167, dy/dx=-0.007263 2,4: dx=599877139, dy=-1518167, dy/dx=-0.002531 2,5: dx=83507788, dy=536942027, dy/dx=6.429844 2,6: dx=803166240, dy=957067221, dy/dx=1.191618 3,4: dx=390851003, dy=0, dy/dx=0.000000 3,5: dx=-125518348, dy=538460194, dy/dx=-4.289892 3,6: dx=594140104, dy=958585388, dy/dx=1.613400 4,5: dx=-516369351, dy=538460194, dy/dx=-1.042781 4,6: dx=203289101, dy=958585388, dy/dx=4.715380 5,6: dx=719658452, dy=420125194, dy/dx=0.583784 Here are the 12 pairs of edges which allegedly intersect: 0: 0,2;1,3 1: 0,2;1,4 2: 0,3;1,4 3: 0,5;1,4 4: 0,5;2,4 5: 0,5;2,6 6: 0,5;3,6 7: 2,4;3,5 8: 2,4;3,6 9: 2,6;3,5 10: 2,6;4,5 11: 3,6;4,5 Unfortunately, I don't have any way to turn this into a graphic. All I can see are lists of numbers. If you, or anyone else reading this, has a way, the bogus or missing crossing should immediately be evident. With 2 billion sets, 21 edges per set, and all coordinates being 31-bit positive integers, I should get about 20 horizontal lines and about 20 vertical lines if the (pseudo-)random number generator is good. I got 18 horizontal lines and 21 vertical lines, which are in good agreement with this. (I discarded the 21 sets with vertical lines.) One curiosity is that of the 18 horizontal lines in the 2 billion sets, 4 of them were in the 21 even-RCN sets, including the set above. So whatever is going wrong probably has something to do with that. (Odds of that being a coincidence are on the order of 10^-32.) But that can't be the whole of it, since 17 of the 21 even-RCN sets did not have horizontal lines, and 14 of the horizontal lines were in odd-RCN sets. I can email you (or anyone else interested) the other 20 even-RCN sets too. I won't bore the whole of math-fun with them.