On 24/07/2020 00:27, Keith F. Lynch wrote: [me:]
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.
[Keith:]
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.)
Hmm. Some other problem, then.
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
Looks to me like it's missing 0--5 intersecting 3--4. (3--4 is exactly horizontal. 0 is below, 5 is above. The lines 5--3, 5--0, 5--4 are all "southeasterly" since 5 is left of the other points and above them. Their gradients are, respectively, -4.3, -1.8, -1.1, so 5--0 is between 5--3 and 5--4. So it should meet 3--4. Easier to see with a picture, but you can check those claims using just the numbers.) But that isn't the only missing one. It's also missing _four_ intersections involving 1--6. (It should meet 0--5, 2--5, 3--5, and 4--5.) I think those are all the misses. I don't see any spurious intersections. It's not obvious to me what sort of bug would cause exactly these intersections to be missed. There's an almost-degenerate triangle (2,3,4) and a perfectly horizontal edge (3--4) and maybe that's somehow related to the missing 0--5/3--4, but the other errors don't seem to have anything to do with either of those unusual features. -- g