Re: [math-fun] Number of ways to pick 4 points from an m X n grid?
Neil Sloane <njasloane@gmail.com> wrote:
If we take an m X n rectangular grid of points, and choose four of them (in binomial(m*n,4) ways), there are four possibilities:
(i) the 4 points are collinear, (ii) 3 points are collinear and one point is not on that line, (iii) 3 points form a triangle of positive area and the other point is in the interior of that triangle, (iv) the 4 points form a convex quadrilateral of nonzero area.
. . .
Which is more likely, (iii) or (iv)?
This inspired me to look at the limiting case where m and n are large. Your i and ii disappear. The values of iii and iv don't depend on the aspect ratio of the rectangle. I'm not smart enough to find a closed-form solution. (Is one known?) I generated 64 billion (pseudo-)random sets of four points in a square, using Unix's "random()" function, which generates 31-bit integers. Since that function repeats after about 2^35 (about 34 billion), after every 2 billion sets (16 billion random numbers), I exclusive-ored every random() with a different row of an order-32 Hadamard matrix (with the -1s turned into 0s, and the first column (which was all 1s) stripped off). Every one of the 32 rows differs in exactly 16 bit positions from every other of the 32 rows. I was amused, when I went searching for Hadamard matrices, that I found a table of them on your website. So, how do I determine, given the x and y coordinates of four points, whether they form a convex quadrilateral or not? After some thought, I decided to check, for every one of the six line segments between two of the four points, whether it intersects the unique other segment which has no endpoints in common with it. If they intersect, it's a convex quadrilateral. If they don't, it's a triangle with a point inside. That's 3 checks, not 6, since if I know whether A intersects B, I don't need to check whether B intersects A. I get triangles 0.305556 of the time, and convex quadrilaterals 0.694444 of the time. (The last digit may be off by 1.) In 193 of the 64 billion cases, one of the lines was vertical, and my program divided by zero. To speed things up, I didn't bother to special-case that, or even to figure out what the program would do there, since whatever it did would be lost in the noise, changing at worst the 9th digit of a 6 digit number. I also checked for parallel lines, the other possible source for division by zero. But there were never any parallel lines. But wait, there's more! If the four points happened to all be within the circle inscribed in the square, I also used them to find the solution for a circle instead of a rectangle. This time I got a triangle 0.295517 of the time, and a convex quadrilateral 0.704483 of the time. (Again, the last digit may be off by 1.) This was from 24352319646 circles, compared to an expected (pi/4)^4 * 64 billion = 24352272758 circles. Those numbers agree to six digits, or two parts in a million, which gives me confidence in the random number generator. But wait, there's more! That was so much fun, I decided to go one better. *Five* points. There are three non-infinitesimal possibilities: A triangle with two points in it, a convex quadrilateral with one point in it, or a convex pentagon. With that many points per set, the program was generating random numbers like they were going out of style. So I used a new row of the Hadamard matrix every billion sets, for a total of just 32 billion sets. Nevertheless, with the additional computation per set, the program took longer to run than the 4-point program. Again, I counted intersections between line segments which didn't share any endpoint. This time there were 15, rather than 3, such tests to be made per set. If there's 1 intersection, it's a triangle with two points in it. If there are 3 intersections, it's a convex quadrilateral with one point in it. It there are 5 intersections, it's a convex pentagon. There is never any other number of intersections. This time there were 165 vertical lines. Still no parallel lines. And here are the results: Triangle: 0.104167 Quadrilateral: 0.555559 Pentagon: 0.340274 That's within a rectangular boundary. Here are the results for a circular boundary: Triangle: 0.094992 Quadrilateral: 0.548827 Pentagon: 0.356181 That's with 9563216295 circles, vs. an expected (pi/4)^5 * 32 billion = 9563115149 circles, the same to within about 10 parts in a million. Higher polygons? The number of pairs of segments which share no endpoints seems to be given by A050534, with an offset. So, 45 for six points, 105 for seven, etc. What's the limiting case? For N points, where N is large, just how unlikely is it that they comprise a convex N-gon? And what's the expected order of the bounding polygon? Does it scale with the square root of N? With the natural log of N? Has anyone explored this stuff? Thanks.
Keith, Very interesting! I will have to study your message carefully, but I just wanted to mention something Ed Pegg pointed out. Sylvester looked at this question, see https://mathworld.wolfram.com/SylvestersFour-PointProblem.html For a square, his theorem is that the prob. of getting a convex quadrilateral is 25/36 , which is exactly the value you found! On Sun, Jun 28, 2020 at 11:05 AM Keith F. Lynch <kfl@keithlynch.net> wrote:
Neil Sloane <njasloane@gmail.com> wrote:
If we take an m X n rectangular grid of points, and choose four of them (in binomial(m*n,4) ways), there are four possibilities:
(i) the 4 points are collinear, (ii) 3 points are collinear and one point is not on that line, (iii) 3 points form a triangle of positive area and the other point is in the interior of that triangle, (iv) the 4 points form a convex quadrilateral of nonzero area.
. . .
Which is more likely, (iii) or (iv)?
This inspired me to look at the limiting case where m and n are large. Your i and ii disappear. The values of iii and iv don't depend on the aspect ratio of the rectangle.
I'm not smart enough to find a closed-form solution. (Is one known?)
I generated 64 billion (pseudo-)random sets of four points in a square, using Unix's "random()" function, which generates 31-bit integers. Since that function repeats after about 2^35 (about 34 billion), after every 2 billion sets (16 billion random numbers), I exclusive-ored every random() with a different row of an order-32 Hadamard matrix (with the -1s turned into 0s, and the first column (which was all 1s) stripped off). Every one of the 32 rows differs in exactly 16 bit positions from every other of the 32 rows. I was amused, when I went searching for Hadamard matrices, that I found a table of them on your website.
So, how do I determine, given the x and y coordinates of four points, whether they form a convex quadrilateral or not? After some thought, I decided to check, for every one of the six line segments between two of the four points, whether it intersects the unique other segment which has no endpoints in common with it. If they intersect, it's a convex quadrilateral. If they don't, it's a triangle with a point inside. That's 3 checks, not 6, since if I know whether A intersects B, I don't need to check whether B intersects A.
I get triangles 0.305556 of the time, and convex quadrilaterals 0.694444 of the time. (The last digit may be off by 1.)
In 193 of the 64 billion cases, one of the lines was vertical, and my program divided by zero. To speed things up, I didn't bother to special-case that, or even to figure out what the program would do there, since whatever it did would be lost in the noise, changing at worst the 9th digit of a 6 digit number.
I also checked for parallel lines, the other possible source for division by zero. But there were never any parallel lines.
But wait, there's more!
If the four points happened to all be within the circle inscribed in the square, I also used them to find the solution for a circle instead of a rectangle. This time I got a triangle 0.295517 of the time, and a convex quadrilateral 0.704483 of the time. (Again, the last digit may be off by 1.) This was from 24352319646 circles, compared to an expected (pi/4)^4 * 64 billion = 24352272758 circles. Those numbers agree to six digits, or two parts in a million, which gives me confidence in the random number generator.
But wait, there's more!
That was so much fun, I decided to go one better. *Five* points. There are three non-infinitesimal possibilities: A triangle with two points in it, a convex quadrilateral with one point in it, or a convex pentagon.
With that many points per set, the program was generating random numbers like they were going out of style. So I used a new row of the Hadamard matrix every billion sets, for a total of just 32 billion sets. Nevertheless, with the additional computation per set, the program took longer to run than the 4-point program.
Again, I counted intersections between line segments which didn't share any endpoint. This time there were 15, rather than 3, such tests to be made per set. If there's 1 intersection, it's a triangle with two points in it. If there are 3 intersections, it's a convex quadrilateral with one point in it. It there are 5 intersections, it's a convex pentagon. There is never any other number of intersections.
This time there were 165 vertical lines. Still no parallel lines.
And here are the results:
Triangle: 0.104167 Quadrilateral: 0.555559 Pentagon: 0.340274
That's within a rectangular boundary. Here are the results for a circular boundary:
Triangle: 0.094992 Quadrilateral: 0.548827 Pentagon: 0.356181
That's with 9563216295 circles, vs. an expected (pi/4)^5 * 32 billion = 9563115149 circles, the same to within about 10 parts in a million.
Higher polygons? The number of pairs of segments which share no endpoints seems to be given by A050534, with an offset. So, 45 for six points, 105 for seven, etc.
What's the limiting case? For N points, where N is large, just how unlikely is it that they comprise a convex N-gon? And what's the expected order of the bounding polygon? Does it scale with the square root of N? With the natural log of N? Has anyone explored this stuff? Thanks.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Interesting. Last week I ran my program to enumerate and classify sets of 4 points chosen from an m x n grid out to 349x349, and placed the results here: http://iq0.com/lq.txt In a 349x349 grid, there are 6,366,733,094,048,270,910 strictly convex quads out of 9,170,030,499,095,875,150 total. The fraction is 0.6942979, just a little shy of Sylvester's 25/36. The deficit is explained by the not quite negligible counts of quads with at least 3 collinear points. If you include them with the strictly convex quads, the ratio is 0.6945982, slightly more than 25/36. BTW, my program took less than 4 days to do these counts. That's a speedup of several million times over my initial, naive program. I stopped at 349x349 because that's the biggest number for which binom(m*m,4)<2^63. Multi-precision counters won't help much -- run time is proportional to the cube of m*n, I think, so doubling up to 700x700 will take several months to run, and I'm out of ideas about how to speed it up. On Sun, Jun 28, 2020 at 8:05 AM Keith F. Lynch <kfl@keithlynch.net> wrote:
Neil Sloane <njasloane@gmail.com> wrote:
If we take an m X n rectangular grid of points, and choose four of them (in binomial(m*n,4) ways), there are four possibilities:
(i) the 4 points are collinear, (ii) 3 points are collinear and one point is not on that line, (iii) 3 points form a triangle of positive area and the other point is in the interior of that triangle, (iv) the 4 points form a convex quadrilateral of nonzero area.
. . .
Which is more likely, (iii) or (iv)?
This inspired me to look at the limiting case where m and n are large. Your i and ii disappear. The values of iii and iv don't depend on the aspect ratio of the rectangle.
I'm not smart enough to find a closed-form solution. (Is one known?)
I generated 64 billion (pseudo-)random sets of four points in a square, using Unix's "random()" function, which generates 31-bit integers. Since that function repeats after about 2^35 (about 34 billion), after every 2 billion sets (16 billion random numbers), I exclusive-ored every random() with a different row of an order-32 Hadamard matrix (with the -1s turned into 0s, and the first column (which was all 1s) stripped off). Every one of the 32 rows differs in exactly 16 bit positions from every other of the 32 rows. I was amused, when I went searching for Hadamard matrices, that I found a table of them on your website.
So, how do I determine, given the x and y coordinates of four points, whether they form a convex quadrilateral or not? After some thought, I decided to check, for every one of the six line segments between two of the four points, whether it intersects the unique other segment which has no endpoints in common with it. If they intersect, it's a convex quadrilateral. If they don't, it's a triangle with a point inside. That's 3 checks, not 6, since if I know whether A intersects B, I don't need to check whether B intersects A.
I get triangles 0.305556 of the time, and convex quadrilaterals 0.694444 of the time. (The last digit may be off by 1.)
In 193 of the 64 billion cases, one of the lines was vertical, and my program divided by zero. To speed things up, I didn't bother to special-case that, or even to figure out what the program would do there, since whatever it did would be lost in the noise, changing at worst the 9th digit of a 6 digit number.
I also checked for parallel lines, the other possible source for division by zero. But there were never any parallel lines.
But wait, there's more!
If the four points happened to all be within the circle inscribed in the square, I also used them to find the solution for a circle instead of a rectangle. This time I got a triangle 0.295517 of the time, and a convex quadrilateral 0.704483 of the time. (Again, the last digit may be off by 1.) This was from 24352319646 circles, compared to an expected (pi/4)^4 * 64 billion = 24352272758 circles. Those numbers agree to six digits, or two parts in a million, which gives me confidence in the random number generator.
But wait, there's more!
That was so much fun, I decided to go one better. *Five* points. There are three non-infinitesimal possibilities: A triangle with two points in it, a convex quadrilateral with one point in it, or a convex pentagon.
With that many points per set, the program was generating random numbers like they were going out of style. So I used a new row of the Hadamard matrix every billion sets, for a total of just 32 billion sets. Nevertheless, with the additional computation per set, the program took longer to run than the 4-point program.
Again, I counted intersections between line segments which didn't share any endpoint. This time there were 15, rather than 3, such tests to be made per set. If there's 1 intersection, it's a triangle with two points in it. If there are 3 intersections, it's a convex quadrilateral with one point in it. It there are 5 intersections, it's a convex pentagon. There is never any other number of intersections.
This time there were 165 vertical lines. Still no parallel lines.
And here are the results:
Triangle: 0.104167 Quadrilateral: 0.555559 Pentagon: 0.340274
That's within a rectangular boundary. Here are the results for a circular boundary:
Triangle: 0.094992 Quadrilateral: 0.548827 Pentagon: 0.356181
That's with 9563216295 circles, vs. an expected (pi/4)^5 * 32 billion = 9563115149 circles, the same to within about 10 parts in a million.
Higher polygons? The number of pairs of segments which share no endpoints seems to be given by A050534, with an offset. So, 45 for six points, 105 for seven, etc.
What's the limiting case? For N points, where N is large, just how unlikely is it that they comprise a convex N-gon? And what's the expected order of the bounding polygon? Does it scale with the square root of N? With the natural log of N? Has anyone explored this stuff? Thanks.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Keith F. Lynch -
Neil Sloane -
Tom Duff