Re: [math-fun] Random nonempty intersection of cube and plane, revisited
Sorry it took me a while to finish my program that finds the average perimeters and areas of the intersection of a plane with a cube. On July 28th, I wrote: Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong. This got me the correct perimeter length. Correct as supported by the program's agreeing with Fred Lunnon's and my ideas of what the smallest and largest perimeters should be for each n-gon. Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries. Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others already in the table. So for the largest possible n, 6, 60 tries. On July 29th I wrote: Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together. This should have worked. I spent most of my time trying, without success, to figure out why it didn't work. I knew it wasn't working because I was getting impossibly large areas. (Except for triangles, where it appeared to be correct, given the maximum area it found.) I was hampered in debugging by the fact that I have no way of generating graphics. All I have to look at are lists of numbers. And I'm not a visual thinker, anyway. Eventually, I figured it must be that I was somehow mistaken that the sequence of vertices with the smallest sum of successive distances was the actual perimeter. I couldn't visualize how that could possibly be, but visualization isn't my strong suit. Yes, the perimeter maxima were correct, but that's no surprise given that a hypothetical incorrect vertex order with a smaller distance sum wouldn't affect that maximum. I looked forward to finding an exception, then drawing it by hand. So I implemented a variant of James Propp's suggestion that I rotate the polygon into the x,y plane, then convert from rectangular to polar coordinates, with the centroid as the origin, and sort by theta. Since at that time I only cared about the order of vertices, I instead simply discarded the z coordinate rather than doing a 3D rotation. (I am perhaps irrationally prejudiced against unnecessary trigonometry, as I'm under the perhaps outdated impression that trig makes programs very slow.) Much to my surprise, I discovered that the orders were the same. (At least for all of ten million random planes.) The flaw in my area algorithm was elsewhere. I continued looking for it until I started running out of time. (James Propp's talk is on August 7th, and today is the 6th.) Then I tried getting the area from my projection into the x,y plane, using the shoelace formula (which was suggested by both James Propp and Tom Duff). The projection is obviously going to be foreshortened, so I tried multiplying it by the slope of the original polygon to fix it. Apparently I computed the slope wrong, as the areas of triangles (hence presumably also all other figures) were wrong. Fortunately, Tom Duff also said, "In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares." Since it was easy to adapt my code which projected into the x,y plane and worked there into doing the same with the other two orthogonal planes, so I did it that way. Then I had a tenacious bug that was due to the modulo function in C being broken. -1 mod 3 should be 2, not -1. Once I changed at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3])); to j1 = (j-1)%g; if (j1 < 0) j1 += g; at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3])); it started working perfectly. (That's the shoelace formula.) In retrospect I should have documented better, used more meaningful variable names, and unrolled those nested subscripts. But the program started two years ago as a quick and dirty hack to measure the average number of edges of the intersection polygon, so I used "alpine programming," by analogy with "alpine style mountain climbing," which means not bothering with those tedious base camps and pre-positioning supplies, but instead just racing for the summit. In my defense, mountains, unlike programming tasks, seldom suddenly get much taller. Anyhow, without further ado, here are the results, based on the average of two runs of a billion random planes. Again, the cube's side length is 2. Smallest, average, and largest perimeters: 3 sides: 0.0000 3.0613 8.4736 4 sides: 4.0001 7.1700 9.6550 5 sides: 6.8314 8.2032 9.6521 6 sides: 8.4853 8.6827 9.6511 All over average perimeter: 6.2841 Smallest, average, and largest areas: 3 sides: 0.0000 0.5496 3.4546 4 sides: 0.0001 3.2519 6.9252 5 sides: 3.0088 4.6743 6.9218 6 sides: 5.1975 5.8310 6.9240 All over average area: 2.8819 Proportion of each polygon type: 3 sides: 27.97% 4 sides: 48.68% 5 sides: 18.70% 6 sides: 4.65% I'm CCing James Propp so that he'll get this in time for tomorrow's talk even if he's on the digest option and no digest goes out before that talk. Tomorrow I'll return to trying to figure out why my original area formula isn't working.
Thanks, Keith! Does your cube have side-length 1 or side-length 2? Jim On Tue, Aug 6, 2019 at 10:39 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Sorry it took me a while to finish my program that finds the average perimeters and areas of the intersection of a plane with a cube.
On July 28th, I wrote:
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong.
This got me the correct perimeter length. Correct as supported by the program's agreeing with Fred Lunnon's and my ideas of what the smallest and largest perimeters should be for each n-gon.
Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries.
Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others already in the table. So for the largest possible n, 6, 60 tries.
On July 29th I wrote:
Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together.
This should have worked. I spent most of my time trying, without success, to figure out why it didn't work. I knew it wasn't working because I was getting impossibly large areas. (Except for triangles, where it appeared to be correct, given the maximum area it found.) I was hampered in debugging by the fact that I have no way of generating graphics. All I have to look at are lists of numbers. And I'm not a visual thinker, anyway.
Eventually, I figured it must be that I was somehow mistaken that the sequence of vertices with the smallest sum of successive distances was the actual perimeter. I couldn't visualize how that could possibly be, but visualization isn't my strong suit. Yes, the perimeter maxima were correct, but that's no surprise given that a hypothetical incorrect vertex order with a smaller distance sum wouldn't affect that maximum.
I looked forward to finding an exception, then drawing it by hand. So I implemented a variant of James Propp's suggestion that I rotate the polygon into the x,y plane, then convert from rectangular to polar coordinates, with the centroid as the origin, and sort by theta. Since at that time I only cared about the order of vertices, I instead simply discarded the z coordinate rather than doing a 3D rotation. (I am perhaps irrationally prejudiced against unnecessary trigonometry, as I'm under the perhaps outdated impression that trig makes programs very slow.)
Much to my surprise, I discovered that the orders were the same. (At least for all of ten million random planes.) The flaw in my area algorithm was elsewhere. I continued looking for it until I started running out of time. (James Propp's talk is on August 7th, and today is the 6th.) Then I tried getting the area from my projection into the x,y plane, using the shoelace formula (which was suggested by both James Propp and Tom Duff). The projection is obviously going to be foreshortened, so I tried multiplying it by the slope of the original polygon to fix it. Apparently I computed the slope wrong, as the areas of triangles (hence presumably also all other figures) were wrong.
Fortunately, Tom Duff also said, "In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares." Since it was easy to adapt my code which projected into the x,y plane and worked there into doing the same with the other two orthogonal planes, so I did it that way.
Then I had a tenacious bug that was due to the modulo function in C being broken. -1 mod 3 should be 2, not -1.
Once I changed
at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3]));
to
j1 = (j-1)%g; if (j1 < 0) j1 += g; at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3]));
it started working perfectly.
(That's the shoelace formula.)
In retrospect I should have documented better, used more meaningful variable names, and unrolled those nested subscripts. But the program started two years ago as a quick and dirty hack to measure the average number of edges of the intersection polygon, so I used "alpine programming," by analogy with "alpine style mountain climbing," which means not bothering with those tedious base camps and pre-positioning supplies, but instead just racing for the summit. In my defense, mountains, unlike programming tasks, seldom suddenly get much taller.
Anyhow, without further ado, here are the results, based on the average of two runs of a billion random planes. Again, the cube's side length is 2.
Smallest, average, and largest perimeters: 3 sides: 0.0000 3.0613 8.4736 4 sides: 4.0001 7.1700 9.6550 5 sides: 6.8314 8.2032 9.6521 6 sides: 8.4853 8.6827 9.6511
All over average perimeter: 6.2841
Smallest, average, and largest areas: 3 sides: 0.0000 0.5496 3.4546 4 sides: 0.0001 3.2519 6.9252 5 sides: 3.0088 4.6743 6.9218 6 sides: 5.1975 5.8310 6.9240
All over average area: 2.8819
Proportion of each polygon type: 3 sides: 27.97% 4 sides: 48.68% 5 sides: 18.70% 6 sides: 4.65%
I'm CCing James Propp so that he'll get this in time for tomorrow's talk even if he's on the digest option and no digest goes out before that talk.
Tomorrow I'll return to trying to figure out why my original area formula isn't working.
Yes! [ More informatively, KFL & WFL cube side length = 2. ] WFL On 8/7/19, James Propp <jamespropp@gmail.com> wrote:
Thanks, Keith!
Does your cube have side-length 1 or side-length 2?
Jim
On Tue, Aug 6, 2019 at 10:39 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Sorry it took me a while to finish my program that finds the average perimeters and areas of the intersection of a plane with a cube.
On July 28th, I wrote:
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong.
This got me the correct perimeter length. Correct as supported by the program's agreeing with Fred Lunnon's and my ideas of what the smallest and largest perimeters should be for each n-gon.
Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries.
Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others already in the table. So for the largest possible n, 6, 60 tries.
On July 29th I wrote:
Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together.
This should have worked. I spent most of my time trying, without success, to figure out why it didn't work. I knew it wasn't working because I was getting impossibly large areas. (Except for triangles, where it appeared to be correct, given the maximum area it found.) I was hampered in debugging by the fact that I have no way of generating graphics. All I have to look at are lists of numbers. And I'm not a visual thinker, anyway.
Eventually, I figured it must be that I was somehow mistaken that the sequence of vertices with the smallest sum of successive distances was the actual perimeter. I couldn't visualize how that could possibly be, but visualization isn't my strong suit. Yes, the perimeter maxima were correct, but that's no surprise given that a hypothetical incorrect vertex order with a smaller distance sum wouldn't affect that maximum.
I looked forward to finding an exception, then drawing it by hand. So I implemented a variant of James Propp's suggestion that I rotate the polygon into the x,y plane, then convert from rectangular to polar coordinates, with the centroid as the origin, and sort by theta. Since at that time I only cared about the order of vertices, I instead simply discarded the z coordinate rather than doing a 3D rotation. (I am perhaps irrationally prejudiced against unnecessary trigonometry, as I'm under the perhaps outdated impression that trig makes programs very slow.)
Much to my surprise, I discovered that the orders were the same. (At least for all of ten million random planes.) The flaw in my area algorithm was elsewhere. I continued looking for it until I started running out of time. (James Propp's talk is on August 7th, and today is the 6th.) Then I tried getting the area from my projection into the x,y plane, using the shoelace formula (which was suggested by both James Propp and Tom Duff). The projection is obviously going to be foreshortened, so I tried multiplying it by the slope of the original polygon to fix it. Apparently I computed the slope wrong, as the areas of triangles (hence presumably also all other figures) were wrong.
Fortunately, Tom Duff also said, "In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares." Since it was easy to adapt my code which projected into the x,y plane and worked there into doing the same with the other two orthogonal planes, so I did it that way.
Then I had a tenacious bug that was due to the modulo function in C being broken. -1 mod 3 should be 2, not -1.
Once I changed
at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3]));
to
j1 = (j-1)%g; if (j1 < 0) j1 += g; at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3]));
it started working perfectly.
(That's the shoelace formula.)
In retrospect I should have documented better, used more meaningful variable names, and unrolled those nested subscripts. But the program started two years ago as a quick and dirty hack to measure the average number of edges of the intersection polygon, so I used "alpine programming," by analogy with "alpine style mountain climbing," which means not bothering with those tedious base camps and pre-positioning supplies, but instead just racing for the summit. In my defense, mountains, unlike programming tasks, seldom suddenly get much taller.
Anyhow, without further ado, here are the results, based on the average of two runs of a billion random planes. Again, the cube's side length is 2.
Smallest, average, and largest perimeters: 3 sides: 0.0000 3.0613 8.4736 4 sides: 4.0001 7.1700 9.6550 5 sides: 6.8314 8.2032 9.6521 6 sides: 8.4853 8.6827 9.6511
All over average perimeter: 6.2841
Smallest, average, and largest areas: 3 sides: 0.0000 0.5496 3.4546 4 sides: 0.0001 3.2519 6.9252 5 sides: 3.0088 4.6743 6.9218 6 sides: 5.1975 5.8310 6.9240
All over average area: 2.8819
Proportion of each polygon type: 3 sides: 27.97% 4 sides: 48.68% 5 sides: 18.70% 6 sides: 4.65%
I'm CCing James Propp so that he'll get this in time for tomorrow's talk even if he's on the digest option and no digest goes out before that talk.
Tomorrow I'll return to trying to figure out why my original area formula isn't working.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Since the volume of the cube of side-length 2 is 8, and since the mean width is (a+b+c)/2 = (2+2+2)/2 = 3, the average cross-sectional area should be 8/3 ~ 2.6667. Keith’s 2.8819 seems awfully far off the mark (especially in comparison with his suggestively accurate estimate 4.0004 from two years ago). Jim On Wed, Aug 7, 2019 at 1:12 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Yes! [ More informatively, KFL & WFL cube side length = 2. ] WFL
On 8/7/19, James Propp <jamespropp@gmail.com> wrote:
Thanks, Keith!
Does your cube have side-length 1 or side-length 2?
Jim
On Tue, Aug 6, 2019 at 10:39 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Sorry it took me a while to finish my program that finds the average perimeters and areas of the intersection of a plane with a cube.
On July 28th, I wrote:
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong.
This got me the correct perimeter length. Correct as supported by the program's agreeing with Fred Lunnon's and my ideas of what the smallest and largest perimeters should be for each n-gon.
Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries.
Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others already in the table. So for the largest possible n, 6, 60 tries.
On July 29th I wrote:
Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together.
This should have worked. I spent most of my time trying, without success, to figure out why it didn't work. I knew it wasn't working because I was getting impossibly large areas. (Except for triangles, where it appeared to be correct, given the maximum area it found.) I was hampered in debugging by the fact that I have no way of generating graphics. All I have to look at are lists of numbers. And I'm not a visual thinker, anyway.
Eventually, I figured it must be that I was somehow mistaken that the sequence of vertices with the smallest sum of successive distances was the actual perimeter. I couldn't visualize how that could possibly be, but visualization isn't my strong suit. Yes, the perimeter maxima were correct, but that's no surprise given that a hypothetical incorrect vertex order with a smaller distance sum wouldn't affect that maximum.
I looked forward to finding an exception, then drawing it by hand. So I implemented a variant of James Propp's suggestion that I rotate the polygon into the x,y plane, then convert from rectangular to polar coordinates, with the centroid as the origin, and sort by theta. Since at that time I only cared about the order of vertices, I instead simply discarded the z coordinate rather than doing a 3D rotation. (I am perhaps irrationally prejudiced against unnecessary trigonometry, as I'm under the perhaps outdated impression that trig makes programs very slow.)
Much to my surprise, I discovered that the orders were the same. (At least for all of ten million random planes.) The flaw in my area algorithm was elsewhere. I continued looking for it until I started running out of time. (James Propp's talk is on August 7th, and today is the 6th.) Then I tried getting the area from my projection into the x,y plane, using the shoelace formula (which was suggested by both James Propp and Tom Duff). The projection is obviously going to be foreshortened, so I tried multiplying it by the slope of the original polygon to fix it. Apparently I computed the slope wrong, as the areas of triangles (hence presumably also all other figures) were wrong.
Fortunately, Tom Duff also said, "In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares." Since it was easy to adapt my code which projected into the x,y plane and worked there into doing the same with the other two orthogonal planes, so I did it that way.
Then I had a tenacious bug that was due to the modulo function in C being broken. -1 mod 3 should be 2, not -1.
Once I changed
at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3]));
to
j1 = (j-1)%g; if (j1 < 0) j1 += g; at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3]));
it started working perfectly.
(That's the shoelace formula.)
In retrospect I should have documented better, used more meaningful variable names, and unrolled those nested subscripts. But the program started two years ago as a quick and dirty hack to measure the average number of edges of the intersection polygon, so I used "alpine programming," by analogy with "alpine style mountain climbing," which means not bothering with those tedious base camps and pre-positioning supplies, but instead just racing for the summit. In my defense, mountains, unlike programming tasks, seldom suddenly get much taller.
Anyhow, without further ado, here are the results, based on the average of two runs of a billion random planes. Again, the cube's side length is 2.
Smallest, average, and largest perimeters: 3 sides: 0.0000 3.0613 8.4736 4 sides: 4.0001 7.1700 9.6550 5 sides: 6.8314 8.2032 9.6521 6 sides: 8.4853 8.6827 9.6511
All over average perimeter: 6.2841
Smallest, average, and largest areas: 3 sides: 0.0000 0.5496 3.4546 4 sides: 0.0001 3.2519 6.9252 5 sides: 3.0088 4.6743 6.9218 6 sides: 5.1975 5.8310 6.9240
All over average area: 2.8819
Proportion of each polygon type: 3 sides: 27.97% 4 sides: 48.68% 5 sides: 18.70% 6 sides: 4.65%
I'm CCing James Propp so that he'll get this in time for tomorrow's talk even if he's on the digest option and no digest goes out before that talk.
Tomorrow I'll return to trying to figure out why my original area formula isn't working.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Generalizing the notion of average to a continuous distribution is not easy. Ideally, all calculations should be checked by alternative integration procedures. Here's another one: Excluding a measure zero set with the plane through one edge, the configuration space can be written as a R=3x1x3 rectangular volume, with a unit-length central edge, between left and right facets, each with three more unit-edge boundaries. Once the three points are chosen, the two edges across adjacent facets are known, and a plane is determined to find the others. With A for area and P for perimeter, let the averages be: Avg(A) = Int_R A*dV, Avg(P) = Int_R P*dV. Are these correct, and how accurately can they be calculated? I am actually interested to work it out and see what happens, but unfortunately I am falling behind on another project and another. Cheers --Brad PS. The same tactic works for the dodecahedron, with R=4x1x4 on pentagonal edges, and similar for other regular polyhedra because their symmetry groups act transitively on the edges and faces. On Wed, Aug 7, 2019 at 12:27 PM James Propp <jamespropp@gmail.com> wrote:
Keith’s 2.8819 seems awfully far off the mark
My suspicion immediately falls on the definition of "random plane intersecting a cube". Here are two possibilities: (1) Pick a uniformly random point in the interior of the cube, then a random line through that point (with direction uniformly distributed on a sphere), and use the plane through the selected point perpendicular to the selected line. (2) Pick a spherically-uniform random line through the origin. There is a closed segment on this line, such that a plane perpendicular to the line cuts the cube only if it intersects the line in that segment. Pick a uniformly random point on that segment, and use the plane that cuts the line perpendicularly at that point. I bet that those two procedures produce different distributions of planes. Both seem reasonable. Maybe Keith and Jim have different definitions in mind? On Wed, Aug 7, 2019 at 1:27 PM James Propp <jamespropp@gmail.com> wrote:
Since the volume of the cube of side-length 2 is 8, and since the mean width is (a+b+c)/2 = (2+2+2)/2 = 3, the average cross-sectional area should be 8/3 ~ 2.6667. Keith’s 2.8819 seems awfully far off the mark (especially in comparison with his suggestively accurate estimate 4.0004 from two years ago).
Jim
On Wed, Aug 7, 2019 at 1:12 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Yes! [ More informatively, KFL & WFL cube side length = 2. ] WFL
On 8/7/19, James Propp <jamespropp@gmail.com> wrote:
Thanks, Keith!
Does your cube have side-length 1 or side-length 2?
Jim
On Tue, Aug 6, 2019 at 10:39 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Sorry it took me a while to finish my program that finds the average perimeters and areas of the intersection of a plane with a cube.
On July 28th, I wrote:
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong.
This got me the correct perimeter length. Correct as supported by the program's agreeing with Fred Lunnon's and my ideas of what the smallest and largest perimeters should be for each n-gon.
Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries.
Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others already in the table. So for the largest possible n, 6, 60 tries.
On July 29th I wrote:
Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together.
This should have worked. I spent most of my time trying, without success, to figure out why it didn't work. I knew it wasn't working because I was getting impossibly large areas. (Except for triangles, where it appeared to be correct, given the maximum area it found.) I was hampered in debugging by the fact that I have no way of generating graphics. All I have to look at are lists of numbers. And I'm not a visual thinker, anyway.
Eventually, I figured it must be that I was somehow mistaken that the sequence of vertices with the smallest sum of successive distances was the actual perimeter. I couldn't visualize how that could possibly be, but visualization isn't my strong suit. Yes, the perimeter maxima were correct, but that's no surprise given that a hypothetical incorrect vertex order with a smaller distance sum wouldn't affect that maximum.
I looked forward to finding an exception, then drawing it by hand. So I implemented a variant of James Propp's suggestion that I rotate the polygon into the x,y plane, then convert from rectangular to polar coordinates, with the centroid as the origin, and sort by theta. Since at that time I only cared about the order of vertices, I instead simply discarded the z coordinate rather than doing a 3D rotation. (I am perhaps irrationally prejudiced against unnecessary trigonometry, as I'm under the perhaps outdated impression that trig makes programs very slow.)
Much to my surprise, I discovered that the orders were the same. (At least for all of ten million random planes.) The flaw in my area algorithm was elsewhere. I continued looking for it until I started running out of time. (James Propp's talk is on August 7th, and today is the 6th.) Then I tried getting the area from my projection into the x,y plane, using the shoelace formula (which was suggested by both James Propp and Tom Duff). The projection is obviously going to be foreshortened, so I tried multiplying it by the slope of the original polygon to fix it. Apparently I computed the slope wrong, as the areas of triangles (hence presumably also all other figures) were wrong.
Fortunately, Tom Duff also said, "In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares." Since it was easy to adapt my code which projected into the x,y plane and worked there into doing the same with the other two orthogonal planes, so I did it that way.
Then I had a tenacious bug that was due to the modulo function in C being broken. -1 mod 3 should be 2, not -1.
Once I changed
at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3]));
to
j1 = (j-1)%g; if (j1 < 0) j1 += g; at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3]));
it started working perfectly.
(That's the shoelace formula.)
In retrospect I should have documented better, used more meaningful variable names, and unrolled those nested subscripts. But the program started two years ago as a quick and dirty hack to measure the average number of edges of the intersection polygon, so I used "alpine programming," by analogy with "alpine style mountain climbing," which means not bothering with those tedious base camps and pre-positioning supplies, but instead just racing for the summit. In my defense, mountains, unlike programming tasks, seldom suddenly get much taller.
Anyhow, without further ado, here are the results, based on the average of two runs of a billion random planes. Again, the cube's side length is 2.
Smallest, average, and largest perimeters: 3 sides: 0.0000 3.0613 8.4736 4 sides: 4.0001 7.1700 9.6550 5 sides: 6.8314 8.2032 9.6521 6 sides: 8.4853 8.6827 9.6511
All over average perimeter: 6.2841
Smallest, average, and largest areas: 3 sides: 0.0000 0.5496 3.4546 4 sides: 0.0001 3.2519 6.9252 5 sides: 3.0088 4.6743 6.9218 6 sides: 5.1975 5.8310 6.9240
All over average area: 2.8819
Proportion of each polygon type: 3 sides: 27.97% 4 sides: 48.68% 5 sides: 18.70% 6 sides: 4.65%
I'm CCing James Propp so that he'll get this in time for tomorrow's talk even if he's on the digest option and no digest goes out before that talk.
Tomorrow I'll return to trying to figure out why my original area formula isn't working.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I shan't try to go into detail at this juncture, but it seems a good opportunity just to raise an issue frequently overlooked by those posing such problems in (as it were) "probabilistic pure geometry". Keith mentioned one source of ambiguity over the meaning of "mean", ie. the choice of integrand function: whether arithmetic, geometric, harmonic, etc. But a subtler difficulty concerns the choice of integration weight: ie. what probability distribution to assign to the phase space (here, planes in 3-space). As soon as the dimension exceeds unity, there will usually be several different "natural" distributions possible, which are in general inequivalent. For example, are the Cartesian coefficients of the plane to be uniform in their range, after reduction via some (arbitrary) normalisation; or instead their direction (qua points on the unit sphere) and distance from the origin? In applied situations there should be extra physical information available to determine such choices; the pure problematist has no such guide. I have made no attempt to establish what respective assumptions may have been made by James and Keith in this case. See https://en.wikipedia.org/wiki/Bertrand_paradox_(probability) Fred Lunnon On 8/7/19, James Propp <jamespropp@gmail.com> wrote:
Since the volume of the cube of side-length 2 is 8, and since the mean width is (a+b+c)/2 = (2+2+2)/2 = 3, the average cross-sectional area should be 8/3 ~ 2.6667. Keith’s 2.8819 seems awfully far off the mark (especially in comparison with his suggestively accurate estimate 4.0004 from two years ago).
Jim
On Wed, Aug 7, 2019 at 1:12 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Yes! [ More informatively, KFL & WFL cube side length = 2. ] WFL
On 8/7/19, James Propp <jamespropp@gmail.com> wrote:
Thanks, Keith!
Does your cube have side-length 1 or side-length 2?
Jim
On Tue, Aug 6, 2019 at 10:39 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Sorry it took me a while to finish my program that finds the average perimeters and areas of the intersection of a plane with a cube.
On July 28th, I wrote:
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong.
This got me the correct perimeter length. Correct as supported by the program's agreeing with Fred Lunnon's and my ideas of what the smallest and largest perimeters should be for each n-gon.
Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries.
Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others already in the table. So for the largest possible n, 6, 60 tries.
On July 29th I wrote:
Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together.
This should have worked. I spent most of my time trying, without success, to figure out why it didn't work. I knew it wasn't working because I was getting impossibly large areas. (Except for triangles, where it appeared to be correct, given the maximum area it found.) I was hampered in debugging by the fact that I have no way of generating graphics. All I have to look at are lists of numbers. And I'm not a visual thinker, anyway.
Eventually, I figured it must be that I was somehow mistaken that the sequence of vertices with the smallest sum of successive distances was the actual perimeter. I couldn't visualize how that could possibly be, but visualization isn't my strong suit. Yes, the perimeter maxima were correct, but that's no surprise given that a hypothetical incorrect vertex order with a smaller distance sum wouldn't affect that maximum.
I looked forward to finding an exception, then drawing it by hand. So I implemented a variant of James Propp's suggestion that I rotate the polygon into the x,y plane, then convert from rectangular to polar coordinates, with the centroid as the origin, and sort by theta. Since at that time I only cared about the order of vertices, I instead simply discarded the z coordinate rather than doing a 3D rotation. (I am perhaps irrationally prejudiced against unnecessary trigonometry, as I'm under the perhaps outdated impression that trig makes programs very slow.)
Much to my surprise, I discovered that the orders were the same. (At least for all of ten million random planes.) The flaw in my area algorithm was elsewhere. I continued looking for it until I started running out of time. (James Propp's talk is on August 7th, and today is the 6th.) Then I tried getting the area from my projection into the x,y plane, using the shoelace formula (which was suggested by both James Propp and Tom Duff). The projection is obviously going to be foreshortened, so I tried multiplying it by the slope of the original polygon to fix it. Apparently I computed the slope wrong, as the areas of triangles (hence presumably also all other figures) were wrong.
Fortunately, Tom Duff also said, "In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares." Since it was easy to adapt my code which projected into the x,y plane and worked there into doing the same with the other two orthogonal planes, so I did it that way.
Then I had a tenacious bug that was due to the modulo function in C being broken. -1 mod 3 should be 2, not -1.
Once I changed
at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3]));
to
j1 = (j-1)%g; if (j1 < 0) j1 += g; at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3]));
it started working perfectly.
(That's the shoelace formula.)
In retrospect I should have documented better, used more meaningful variable names, and unrolled those nested subscripts. But the program started two years ago as a quick and dirty hack to measure the average number of edges of the intersection polygon, so I used "alpine programming," by analogy with "alpine style mountain climbing," which means not bothering with those tedious base camps and pre-positioning supplies, but instead just racing for the summit. In my defense, mountains, unlike programming tasks, seldom suddenly get much taller.
Anyhow, without further ado, here are the results, based on the average of two runs of a billion random planes. Again, the cube's side length is 2.
Smallest, average, and largest perimeters: 3 sides: 0.0000 3.0613 8.4736 4 sides: 4.0001 7.1700 9.6550 5 sides: 6.8314 8.2032 9.6521 6 sides: 8.4853 8.6827 9.6511
All over average perimeter: 6.2841
Smallest, average, and largest areas: 3 sides: 0.0000 0.5496 3.4546 4 sides: 0.0001 3.2519 6.9252 5 sides: 3.0088 4.6743 6.9218 6 sides: 5.1975 5.8310 6.9240
All over average area: 2.8819
Proportion of each polygon type: 3 sides: 27.97% 4 sides: 48.68% 5 sides: 18.70% 6 sides: 4.65%
I'm CCing James Propp so that he'll get this in time for tomorrow's talk even if he's on the digest option and no digest goes out before that talk.
Tomorrow I'll return to trying to figure out why my original area formula isn't working.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Geometric measure theory looks for measures that are invariant with respect to symmetries of the underlying space. For instance, we seek a continuous measure on the set of planes in 3-space that is invariant under translation and rotation. And it turns out to be unique (up to scaling)! That’s the measure I have in mind. Jim On Wed, Aug 7, 2019 at 2:57 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
I shan't try to go into detail at this juncture, but it seems a good opportunity just to raise an issue frequently overlooked by those posing such problems in (as it were) "probabilistic pure geometry".
Keith mentioned one source of ambiguity over the meaning of "mean", ie. the choice of integrand function: whether arithmetic, geometric, harmonic, etc. But a subtler difficulty concerns the choice of integration weight: ie. what probability distribution to assign to the phase space (here, planes in 3-space).
As soon as the dimension exceeds unity, there will usually be several different "natural" distributions possible, which are in general inequivalent. For example, are the Cartesian coefficients of the plane to be uniform in their range, after reduction via some (arbitrary) normalisation; or instead their direction (qua points on the unit sphere) and distance from the origin?
In applied situations there should be extra physical information available to determine such choices; the pure problematist has no such guide. I have made no attempt to establish what respective assumptions may have been made by James and Keith in this case.
See https://en.wikipedia.org/wiki/Bertrand_paradox_(probability)
Fred Lunnon
On 8/7/19, James Propp <jamespropp@gmail.com> wrote:
Since the volume of the cube of side-length 2 is 8, and since the mean width is (a+b+c)/2 = (2+2+2)/2 = 3, the average cross-sectional area should be 8/3 ~ 2.6667. Keith’s 2.8819 seems awfully far off the mark (especially in comparison with his suggestively accurate estimate 4.0004 from two years ago).
Jim
On Wed, Aug 7, 2019 at 1:12 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Yes! [ More informatively, KFL & WFL cube side length = 2. ] WFL
On 8/7/19, James Propp <jamespropp@gmail.com> wrote:
Thanks, Keith!
Does your cube have side-length 1 or side-length 2?
Jim
On Tue, Aug 6, 2019 at 10:39 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Sorry it took me a while to finish my program that finds the average perimeters and areas of the intersection of a plane with a cube.
On July 28th, I wrote:
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong.
This got me the correct perimeter length. Correct as supported by the program's agreeing with Fred Lunnon's and my ideas of what the smallest and largest perimeters should be for each n-gon.
Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries.
Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others already in the table. So for the largest possible n, 6, 60 tries.
On July 29th I wrote:
Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together.
This should have worked. I spent most of my time trying, without success, to figure out why it didn't work. I knew it wasn't working because I was getting impossibly large areas. (Except for triangles, where it appeared to be correct, given the maximum area it found.) I was hampered in debugging by the fact that I have no way of generating graphics. All I have to look at are lists of numbers. And I'm not a visual thinker, anyway.
Eventually, I figured it must be that I was somehow mistaken that the sequence of vertices with the smallest sum of successive distances was the actual perimeter. I couldn't visualize how that could possibly be, but visualization isn't my strong suit. Yes, the perimeter maxima were correct, but that's no surprise given that a hypothetical incorrect vertex order with a smaller distance sum wouldn't affect that maximum.
I looked forward to finding an exception, then drawing it by hand. So I implemented a variant of James Propp's suggestion that I rotate the polygon into the x,y plane, then convert from rectangular to polar coordinates, with the centroid as the origin, and sort by theta. Since at that time I only cared about the order of vertices, I instead simply discarded the z coordinate rather than doing a 3D rotation. (I am perhaps irrationally prejudiced against unnecessary trigonometry, as I'm under the perhaps outdated impression that trig makes programs very slow.)
Much to my surprise, I discovered that the orders were the same. (At least for all of ten million random planes.) The flaw in my area algorithm was elsewhere. I continued looking for it until I started running out of time. (James Propp's talk is on August 7th, and today is the 6th.) Then I tried getting the area from my projection into the x,y plane, using the shoelace formula (which was suggested by both James Propp and Tom Duff). The projection is obviously going to be foreshortened, so I tried multiplying it by the slope of the original polygon to fix it. Apparently I computed the slope wrong, as the areas of triangles (hence presumably also all other figures) were wrong.
Fortunately, Tom Duff also said, "In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares." Since it was easy to adapt my code which projected into the x,y plane and worked there into doing the same with the other two orthogonal planes, so I did it that way.
Then I had a tenacious bug that was due to the modulo function in C being broken. -1 mod 3 should be 2, not -1.
Once I changed
at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3]));
to
j1 = (j-1)%g; if (j1 < 0) j1 += g; at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3]));
it started working perfectly.
(That's the shoelace formula.)
In retrospect I should have documented better, used more meaningful variable names, and unrolled those nested subscripts. But the program started two years ago as a quick and dirty hack to measure the average number of edges of the intersection polygon, so I used "alpine programming," by analogy with "alpine style mountain climbing," which means not bothering with those tedious base camps and pre-positioning supplies, but instead just racing for the summit. In my defense, mountains, unlike programming tasks, seldom suddenly get much taller.
Anyhow, without further ado, here are the results, based on the average of two runs of a billion random planes. Again, the cube's side length is 2.
Smallest, average, and largest perimeters: 3 sides: 0.0000 3.0613 8.4736 4 sides: 4.0001 7.1700 9.6550 5 sides: 6.8314 8.2032 9.6521 6 sides: 8.4853 8.6827 9.6511
All over average perimeter: 6.2841
Smallest, average, and largest areas: 3 sides: 0.0000 0.5496 3.4546 4 sides: 0.0001 3.2519 6.9252 5 sides: 3.0088 4.6743 6.9218 6 sides: 5.1975 5.8310 6.9240
All over average area: 2.8819
Proportion of each polygon type: 3 sides: 27.97% 4 sides: 48.68% 5 sides: 18.70% 6 sides: 4.65%
I'm CCing James Propp so that he'll get this in time for tomorrow's talk even if he's on the digest option and no digest goes out before that talk.
Tomorrow I'll return to trying to figure out why my original area formula isn't working.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I did not know that, and would be interested in hearing how this invariant measure is defined. On Wed, Aug 7, 2019, 6:31 PM James Propp <jamespropp@gmail.com> wrote:
Geometric measure theory looks for measures that are invariant with respect to symmetries of the underlying space. For instance, we seek a continuous measure on the set of planes in 3-space that is invariant under translation and rotation. And it turns out to be unique (up to scaling)! That’s the measure I have in mind.
Jim
On Wed, Aug 7, 2019 at 2:57 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
I shan't try to go into detail at this juncture, but it seems a good opportunity just to raise an issue frequently overlooked by those posing such problems in (as it were) "probabilistic pure geometry".
Keith mentioned one source of ambiguity over the meaning of "mean", ie. the choice of integrand function: whether arithmetic, geometric, harmonic, etc. But a subtler difficulty concerns the choice of integration weight: ie. what probability distribution to assign to the phase space (here, planes in 3-space).
As soon as the dimension exceeds unity, there will usually be several different "natural" distributions possible, which are in general inequivalent. For example, are the Cartesian coefficients of the plane to be uniform in their range, after reduction via some (arbitrary) normalisation; or instead their direction (qua points on the unit sphere) and distance from the origin?
In applied situations there should be extra physical information available to determine such choices; the pure problematist has no such guide. I have made no attempt to establish what respective assumptions may have been made by James and Keith in this case.
See https://en.wikipedia.org/wiki/Bertrand_paradox_(probability)
Fred Lunnon
On 8/7/19, James Propp <jamespropp@gmail.com> wrote:
Since the volume of the cube of side-length 2 is 8, and since the mean width is (a+b+c)/2 = (2+2+2)/2 = 3, the average cross-sectional area should be 8/3 ~ 2.6667. Keith’s 2.8819 seems awfully far off the mark (especially in comparison with his suggestively accurate estimate 4.0004 from two years ago).
Jim
On Wed, Aug 7, 2019 at 1:12 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Yes! [ More informatively, KFL & WFL cube side length = 2. ] WFL
On 8/7/19, James Propp <jamespropp@gmail.com> wrote:
Thanks, Keith!
Does your cube have side-length 1 or side-length 2?
Jim
On Tue, Aug 6, 2019 at 10:39 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Sorry it took me a while to finish my program that finds the average perimeters and areas of the intersection of a plane with a cube.
On July 28th, I wrote:
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong.
This got me the correct perimeter length. Correct as supported by the program's agreeing with Fred Lunnon's and my ideas of what the smallest and largest perimeters should be for each n-gon.
Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries.
Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others already in the table. So for the largest possible n, 6, 60 tries.
On July 29th I wrote:
Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together.
This should have worked. I spent most of my time trying, without success, to figure out why it didn't work. I knew it wasn't working because I was getting impossibly large areas. (Except for triangles, where it appeared to be correct, given the maximum area it found.) I was hampered in debugging by the fact that I have no way of generating graphics. All I have to look at are lists of numbers. And I'm not a visual thinker, anyway.
Eventually, I figured it must be that I was somehow mistaken that the sequence of vertices with the smallest sum of successive distances was the actual perimeter. I couldn't visualize how that could possibly be, but visualization isn't my strong suit. Yes, the perimeter maxima were correct, but that's no surprise given that a hypothetical incorrect vertex order with a smaller distance sum wouldn't affect that maximum.
I looked forward to finding an exception, then drawing it by hand. So I implemented a variant of James Propp's suggestion that I rotate the polygon into the x,y plane, then convert from rectangular to polar coordinates, with the centroid as the origin, and sort by theta. Since at that time I only cared about the order of vertices, I instead simply discarded the z coordinate rather than doing a 3D rotation. (I am perhaps irrationally prejudiced against unnecessary trigonometry, as I'm under the perhaps outdated impression that trig makes programs very slow.)
Much to my surprise, I discovered that the orders were the same. (At least for all of ten million random planes.) The flaw in my area algorithm was elsewhere. I continued looking for it until I started running out of time. (James Propp's talk is on August 7th, and today is the 6th.) Then I tried getting the area from my projection into the x,y plane, using the shoelace formula (which was suggested by both James Propp and Tom Duff). The projection is obviously going to be foreshortened, so I tried multiplying it by the slope of the original polygon to fix it. Apparently I computed the slope wrong, as the areas of triangles (hence presumably also all other figures) were wrong.
Fortunately, Tom Duff also said, "In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares." Since it was easy to adapt my code which projected into the x,y plane and worked there into doing the same with the other two orthogonal planes, so I did it that way.
Then I had a tenacious bug that was due to the modulo function in C being broken. -1 mod 3 should be 2, not -1.
Once I changed
at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3]));
to
j1 = (j-1)%g; if (j1 < 0) j1 += g; at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3]));
it started working perfectly.
(That's the shoelace formula.)
In retrospect I should have documented better, used more meaningful variable names, and unrolled those nested subscripts. But the program started two years ago as a quick and dirty hack to measure the average number of edges of the intersection polygon, so I used "alpine programming," by analogy with "alpine style mountain climbing," which means not bothering with those tedious base camps and pre-positioning supplies, but instead just racing for the summit. In my defense, mountains, unlike programming tasks, seldom suddenly get much taller.
Anyhow, without further ado, here are the results, based on the average of two runs of a billion random planes. Again, the cube's side length is 2.
Smallest, average, and largest perimeters: 3 sides: 0.0000 3.0613 8.4736 4 sides: 4.0001 7.1700 9.6550 5 sides: 6.8314 8.2032 9.6521 6 sides: 8.4853 8.6827 9.6511
All over average perimeter: 6.2841
Smallest, average, and largest areas: 3 sides: 0.0000 0.5496 3.4546 4 sides: 0.0001 3.2519 6.9252 5 sides: 3.0088 4.6743 6.9218 6 sides: 5.1975 5.8310 6.9240
All over average area: 2.8819
Proportion of each polygon type: 3 sides: 27.97% 4 sides: 48.68% 5 sides: 18.70% 6 sides: 4.65%
I'm CCing James Propp so that he'll get this in time for tomorrow's talk even if he's on the digest option and no digest goes out before that talk.
Tomorrow I'll return to trying to figure out why my original area formula isn't working.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Also interested to hear Jim say “yes” or “no” to the proposals thus far. Allan W. #2 sounds more reasonable than #1, as it is 1-to-1. I also think that Euclidean volume element is okay for my region R, because length elements of the one-boundaries are also Cartesian. (And body-fixed coordinates should circumvent need to check transformation properties relative to ambient space.) The issue of ignoring measure zero sets is a tricky one though, and too little thought on this question could wreck the whole argument. One would probably also want to measure the average perimeter and area of intersections through an entire edge, but that is just an integral from zero to Pi/2 for the cube. Could be a better, easier starting place actually. —Brad
On Aug 7, 2019, at 5:45 PM, Allan Wechsler <acwacw@gmail.com> wrote:
I did not know that, and would be interested in hearing how this invariant measure is defined.
On Wed, Aug 7, 2019, 6:31 PM James Propp <jamespropp@gmail.com> wrote:
Geometric measure theory looks for measures that are invariant with respect to symmetries of the underlying space. For instance, we seek a continuous measure on the set of planes in 3-space that is invariant under translation and rotation. And it turns out to be unique (up to scaling)! That’s the measure I have in mind.
Jim
On Wed, Aug 7, 2019 at 2:57 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
I shan't try to go into detail at this juncture, but it seems a good opportunity just to raise an issue frequently overlooked by those posing such problems in (as it were) "probabilistic pure geometry".
Keith mentioned one source of ambiguity over the meaning of "mean", ie. the choice of integrand function: whether arithmetic, geometric, harmonic, etc. But a subtler difficulty concerns the choice of integration weight: ie. what probability distribution to assign to the phase space (here, planes in 3-space).
As soon as the dimension exceeds unity, there will usually be several different "natural" distributions possible, which are in general inequivalent. For example, are the Cartesian coefficients of the plane to be uniform in their range, after reduction via some (arbitrary) normalisation; or instead their direction (qua points on the unit sphere) and distance from the origin?
In applied situations there should be extra physical information available to determine such choices; the pure problematist has no such guide. I have made no attempt to establish what respective assumptions may have been made by James and Keith in this case.
See https://en.wikipedia.org/wiki/Bertrand_paradox_(probability)
Fred Lunnon
On 8/7/19, James Propp <jamespropp@gmail.com> wrote: Since the volume of the cube of side-length 2 is 8, and since the mean width is (a+b+c)/2 = (2+2+2)/2 = 3, the average cross-sectional area should be 8/3 ~ 2.6667. Keith’s 2.8819 seems awfully far off the mark (especially in comparison with his suggestively accurate estimate 4.0004 from two years ago).
Jim
On Wed, Aug 7, 2019 at 1:12 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Yes! [ More informatively, KFL & WFL cube side length = 2. ] WFL
On 8/7/19, James Propp <jamespropp@gmail.com> wrote: Thanks, Keith!
Does your cube have side-length 1 or side-length 2?
Jim
On Tue, Aug 6, 2019 at 10:39 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
> Sorry it took me a while to finish my program that finds the average > perimeters and areas of the intersection of a plane with a cube. > > On July 28th, I wrote: > > Okay, I think I figured it out. Where n is the order of the > intersection polygon, 3 through 6, there are n intersection points > between the cube and the plane, hence n! possible sequences of > intersection points. Since the polygon is convex, I'm pretty sure > that the correct order to visit the n intersection points, returning > to my starting point (i.e. a Hamiltonian circuit) will simply be the > one with the shortest total distance. Someone please politely tell > me if I'm wrong. > > This got me the correct perimeter length. Correct as supported by > the program's agreeing with Fred Lunnon's and my ideas of what the > smallest and largest perimeters should be for each n-gon. > > Since it doesn't matter which intersection point I start on, I only > have to try (n-1)! sequences. Make that (n-1)!-1, since there are > two correct solutions (the same solution in opposite directions) and > they can't both be in the last place. So for the largest possible > n, 6, 119 tries. > > Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, > 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others > already in the table. So for the largest possible n, 6, 60 tries. > > On July 29th I wrote: > > Once I know the order of the intersection points, all I have to > do is run a line from one intersection point to each of the other > intersection points, to divide the polygon into triangles, then > Heron each of the triangles and add their areas together. > > This should have worked. I spent most of my time trying, without > success, to figure out why it didn't work. I knew it wasn't working > because I was getting impossibly large areas. (Except for triangles, > where it appeared to be correct, given the maximum area it found.) I > was hampered in debugging by the fact that I have no way of generating > graphics. All I have to look at are lists of numbers. And I'm not a > visual thinker, anyway. > > Eventually, I figured it must be that I was somehow mistaken that the > sequence of vertices with the smallest sum of successive distances was > the actual perimeter. I couldn't visualize how that could possibly > be, but visualization isn't my strong suit. Yes, the perimeter maxima > were correct, but that's no surprise given that a hypothetical > incorrect > vertex order with a smaller distance sum wouldn't affect that maximum. > > I looked forward to finding an exception, then drawing it by hand. So > I implemented a variant of James Propp's suggestion that I rotate the > polygon into the x,y plane, then convert from rectangular to polar > coordinates, with the centroid as the origin, and sort by theta. > Since at that time I only cared about the order of vertices, I instead > simply discarded the z coordinate rather than doing a 3D rotation. (I > am perhaps irrationally prejudiced against unnecessary trigonometry, > as I'm under the perhaps outdated impression that trig makes programs > very slow.) > > Much to my surprise, I discovered that the orders were the same. (At > least for all of ten million random planes.) The flaw in my area > algorithm was elsewhere. I continued looking for it until I started > running out of time. (James Propp's talk is on August 7th, and today > is the 6th.) Then I tried getting the area from my projection into > the x,y plane, using the shoelace formula (which was suggested by both > James Propp and Tom Duff). The projection is obviously going to be > foreshortened, so I tried multiplying it by the slope of the original > polygon to fix it. Apparently I computed the slope wrong, as the > areas of triangles (hence presumably also all other figures) were > wrong. > > Fortunately, Tom Duff also said, "In 3 dimensions you can either > rotate everything into the plane or compute the projected areas in > the xy, yz and zx planes and take the square root of the sum of the > squares." Since it was easy to adapt my code which projected into > the x,y plane and worked there into doing the same with the other two > orthogonal planes, so I did it that way. > > Then I had a tenacious bug that was due to the modulo function in C > being broken. -1 mod 3 should be 2, not -1. > > Once I changed > > at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * > (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3])); > > to > > j1 = (j-1)%g; if (j1 < 0) j1 += g; > at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * > (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3])); > > it started working perfectly. > > (That's the shoelace formula.) > > In retrospect I should have documented better, used more meaningful > variable names, and unrolled those nested subscripts. But the program > started two years ago as a quick and dirty hack to measure the average > number of edges of the intersection polygon, so I used "alpine > programming," by analogy with "alpine style mountain climbing," which > means not bothering with those tedious base camps and pre-positioning > supplies, but instead just racing for the summit. In my defense, > mountains, unlike programming tasks, seldom suddenly get much taller. > > Anyhow, without further ado, here are the results, based on the > average of two runs of a billion random planes. Again, the cube's > side length is 2. > > Smallest, average, and largest perimeters: > 3 sides: 0.0000 3.0613 8.4736 > 4 sides: 4.0001 7.1700 9.6550 > 5 sides: 6.8314 8.2032 9.6521 > 6 sides: 8.4853 8.6827 9.6511 > > All over average perimeter: 6.2841 > > Smallest, average, and largest areas: > 3 sides: 0.0000 0.5496 3.4546 > 4 sides: 0.0001 3.2519 6.9252 > 5 sides: 3.0088 4.6743 6.9218 > 6 sides: 5.1975 5.8310 6.9240 > > All over average area: 2.8819 > > Proportion of each polygon type: > 3 sides: 27.97% > 4 sides: 48.68% > 5 sides: 18.70% > 6 sides: 4.65% > > I'm CCing James Propp so that he'll get this in time for tomorrow's > talk even if he's on the digest option and no digest goes out before > that talk. > > Tomorrow I'll return to trying to figure out why my original area > formula isn't working. > _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
@Brad K, I agree -- that occurred to me. And furthermore, I think #2 is more likely to turn out to cohere with Jim's unique-up-to-scaling invariant measure. (The more I think about that measure, the more it flummoxes me. Rotating a plane around a line in that plane by a tiny angle ought to be a tiny move, and invariance means that the choice of rotation axis should not matter. But then, translating a plane perpendicular to itself without changing its orientation can be shown to be a smaller move than any rotation, and is therefore 0, which violates positive definiteness. Flummox, flummox.) On Wed, Aug 7, 2019 at 7:28 PM <bradklee@gmail.com> wrote:
Also interested to hear Jim say “yes” or “no” to the proposals thus far.
Allan W. #2 sounds more reasonable than #1, as it is 1-to-1.
I also think that Euclidean volume element is okay for my region R, because length elements of the one-boundaries are also Cartesian. (And body-fixed coordinates should circumvent need to check transformation properties relative to ambient space.)
The issue of ignoring measure zero sets is a tricky one though, and too little thought on this question could wreck the whole argument.
One would probably also want to measure the average perimeter and area of intersections through an entire edge, but that is just an integral from zero to Pi/2 for the cube. Could be a better, easier starting place actually.
—Brad
On Aug 7, 2019, at 5:45 PM, Allan Wechsler <acwacw@gmail.com> wrote:
I did not know that, and would be interested in hearing how this invariant measure is defined.
On Wed, Aug 7, 2019, 6:31 PM James Propp <jamespropp@gmail.com> wrote:
Geometric measure theory looks for measures that are invariant with respect to symmetries of the underlying space. For instance, we seek a continuous measure on the set of planes in 3-space that is invariant under translation and rotation. And it turns out to be unique (up to scaling)! That’s the measure I have in mind.
Jim
On Wed, Aug 7, 2019 at 2:57 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
I shan't try to go into detail at this juncture, but it seems a good opportunity just to raise an issue frequently overlooked by those posing such problems in (as it were) "probabilistic pure geometry".
Keith mentioned one source of ambiguity over the meaning of "mean", ie. the choice of integrand function: whether arithmetic, geometric, harmonic, etc. But a subtler difficulty concerns the choice of integration weight: ie. what probability distribution to assign to the phase space (here, planes in 3-space).
As soon as the dimension exceeds unity, there will usually be several different "natural" distributions possible, which are in general inequivalent. For example, are the Cartesian coefficients of the plane to be uniform in their range, after reduction via some (arbitrary) normalisation; or instead their direction (qua points on the unit sphere) and distance from the origin?
In applied situations there should be extra physical information available to determine such choices; the pure problematist has no such guide. I have made no attempt to establish what respective assumptions may have been made by James and Keith in this case.
See https://en.wikipedia.org/wiki/Bertrand_paradox_(probability)
Fred Lunnon
On 8/7/19, James Propp <jamespropp@gmail.com> wrote: Since the volume of the cube of side-length 2 is 8, and since the mean width is (a+b+c)/2 = (2+2+2)/2 = 3, the average cross-sectional area should be 8/3 ~ 2.6667. Keith’s 2.8819 seems awfully far off the mark (especially in comparison with his suggestively accurate estimate 4.0004 from two years ago).
Jim
On Wed, Aug 7, 2019 at 1:12 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Yes! [ More informatively, KFL & WFL cube side length = 2. ] WFL
> On 8/7/19, James Propp <jamespropp@gmail.com> wrote: > Thanks, Keith! > > Does your cube have side-length 1 or side-length 2? > > Jim > > On Tue, Aug 6, 2019 at 10:39 PM Keith F. Lynch <kfl@keithlynch.net> wrote: > >> Sorry it took me a while to finish my program that finds the average >> perimeters and areas of the intersection of a plane with a cube. >> >> On July 28th, I wrote: >> >> Okay, I think I figured it out. Where n is the order of the >> intersection polygon, 3 through 6, there are n intersection points >> between the cube and the plane, hence n! possible sequences of >> intersection points. Since the polygon is convex, I'm pretty sure >> that the correct order to visit the n intersection points, returning >> to my starting point (i.e. a Hamiltonian circuit) will simply be the >> one with the shortest total distance. Someone please politely tell >> me if I'm wrong. >> >> This got me the correct perimeter length. Correct as supported by >> the program's agreeing with Fred Lunnon's and my ideas of what the >> smallest and largest perimeters should be for each n-gon. >> >> Since it doesn't matter which intersection point I start on, I only >> have to try (n-1)! sequences. Make that (n-1)!-1, since there are >> two correct solutions (the same solution in opposite directions) and >> they can't both be in the last place. So for the largest possible >> n, 6, 119 tries. >> >> Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, >> 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others >> already in the table. So for the largest possible n, 6, 60 tries. >> >> On July 29th I wrote: >> >> Once I know the order of the intersection points, all I have to >> do is run a line from one intersection point to each of the other >> intersection points, to divide the polygon into triangles, then >> Heron each of the triangles and add their areas together. >> >> This should have worked. I spent most of my time trying, without >> success, to figure out why it didn't work. I knew it wasn't working >> because I was getting impossibly large areas. (Except for triangles, >> where it appeared to be correct, given the maximum area it found.) I >> was hampered in debugging by the fact that I have no way of generating >> graphics. All I have to look at are lists of numbers. And I'm not a >> visual thinker, anyway. >> >> Eventually, I figured it must be that I was somehow mistaken that the >> sequence of vertices with the smallest sum of successive distances was >> the actual perimeter. I couldn't visualize how that could possibly >> be, but visualization isn't my strong suit. Yes, the perimeter maxima >> were correct, but that's no surprise given that a hypothetical >> incorrect >> vertex order with a smaller distance sum wouldn't affect that maximum. >> >> I looked forward to finding an exception, then drawing it by hand. So >> I implemented a variant of James Propp's suggestion that I rotate the >> polygon into the x,y plane, then convert from rectangular to polar >> coordinates, with the centroid as the origin, and sort by theta. >> Since at that time I only cared about the order of vertices, I instead >> simply discarded the z coordinate rather than doing a 3D rotation. (I >> am perhaps irrationally prejudiced against unnecessary trigonometry, >> as I'm under the perhaps outdated impression that trig makes programs >> very slow.) >> >> Much to my surprise, I discovered that the orders were the same. (At >> least for all of ten million random planes.) The flaw in my area >> algorithm was elsewhere. I continued looking for it until I started >> running out of time. (James Propp's talk is on August 7th, and today >> is the 6th.) Then I tried getting the area from my projection into >> the x,y plane, using the shoelace formula (which was suggested by both >> James Propp and Tom Duff). The projection is obviously going to be >> foreshortened, so I tried multiplying it by the slope of the original >> polygon to fix it. Apparently I computed the slope wrong, as the >> areas of triangles (hence presumably also all other figures) were >> wrong. >> >> Fortunately, Tom Duff also said, "In 3 dimensions you can either >> rotate everything into the plane or compute the projected areas in >> the xy, yz and zx planes and take the square root of the sum of the >> squares." Since it was easy to adapt my code which projected into >> the x,y plane and worked there into doing the same with the other two >> orthogonal planes, so I did it that way. >> >> Then I had a tenacious bug that was due to the modulo function in C >> being broken. -1 mod 3 should be 2, not -1. >> >> Once I changed >> >> at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * >> (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3])); >> >> to >> >> j1 = (j-1)%g; if (j1 < 0) j1 += g; >> at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * >> (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3])); >> >> it started working perfectly. >> >> (That's the shoelace formula.) >> >> In retrospect I should have documented better, used more meaningful >> variable names, and unrolled those nested subscripts. But the program >> started two years ago as a quick and dirty hack to measure the average >> number of edges of the intersection polygon, so I used "alpine >> programming," by analogy with "alpine style mountain climbing," which >> means not bothering with those tedious base camps and pre-positioning >> supplies, but instead just racing for the summit. In my defense, >> mountains, unlike programming tasks, seldom suddenly get much taller. >> >> Anyhow, without further ado, here are the results, based on the >> average of two runs of a billion random planes. Again, the cube's >> side length is 2. >> >> Smallest, average, and largest perimeters: >> 3 sides: 0.0000 3.0613 8.4736 >> 4 sides: 4.0001 7.1700 9.6550 >> 5 sides: 6.8314 8.2032 9.6521 >> 6 sides: 8.4853 8.6827 9.6511 >> >> All over average perimeter: 6.2841 >> >> Smallest, average, and largest areas: >> 3 sides: 0.0000 0.5496 3.4546 >> 4 sides: 0.0001 3.2519 6.9252 >> 5 sides: 3.0088 4.6743 6.9218 >> 6 sides: 5.1975 5.8310 6.9240 >> >> All over average area: 2.8819 >> >> Proportion of each polygon type: >> 3 sides: 27.97% >> 4 sides: 48.68% >> 5 sides: 18.70% >> 6 sides: 4.65% >> >> I'm CCing James Propp so that he'll get this in time for tomorrow's >> talk even if he's on the digest option and no digest goes out before >> that talk. >> >> Tomorrow I'll return to trying to figure out why my original area >> formula isn't working. >> > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Wed, Aug 7, 2019 at 7:28 PM <bradklee@gmail.com> wrote:
The issue of ignoring measure zero sets is a tricky one though, and too little thought on this question could wreck the whole argument.
If what we're interested in is the integral of a function with respect to a particular measure, there is nothing tricky about ignoring measure zero sets. If a set has measure 0, the integral is unchanged by integrating a function that has different, arbitrary, values on that set. Andy andy.latto@pobox.com
Andy, In this case the function doesn't have poles, so you are probably right. I still think it's weird that a complete integral can be taken on an incomplete domain, so I'm willing to worry more. Another "problem" is that, after more thought, it seems plausible that the configuration space R would need an odd volume element to match Jim Propp's preferred standard. I think it's still "okay" to start with Cartesian, but would not be surprised if this led to statistical diversity. Also, nice reading of Keith's algorithm, I was confused by the part about "carving", but now I can see from your perspective that it actually sounds right. Is Keith's algorithm on Mathworld? Maybe we could get EW to add a few more equations? Please don't blame Fred for listening to me. We are all trying to have fun and learn more, and it doesn't hurt to double or triple check for quality assurance! Cheers --Brad On Wed, Aug 7, 2019 at 11:28 PM Andy Latto <andy.latto@pobox.com> wrote:
If what we're interested in is the integral of a function with respect to a particular measure, there is nothing tricky about ignoring measure zero sets. If a set has measure 0, the integral is unchanged by integrating a function that has different, arbitrary, values on that set.
Andy andy.latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Here's my code, and its results. That perimeter sure looks close to tau. -tom At 67108864 pts 3.99990034103394 area 2.6665184797472 perim 6.28303082552975 At 134217728 pts 3.9999551102519 area 2.66652574548337 perim 6.28309803073879 At 268435456 pts 3.99998798593879 area 2.66669666495159 perim 6.28329936437473 On Wed, Aug 7, 2019 at 9:47 PM Brad Klee <bradklee@gmail.com> wrote:
Andy,
In this case the function doesn't have poles, so you are probably right. I still think it's weird that a complete integral can be taken on an incomplete domain, so I'm willing to worry more.
Another "problem" is that, after more thought, it seems plausible that the configuration space R would need an odd volume element to match Jim Propp's preferred standard. I think it's still "okay" to start with Cartesian, but would not be surprised if this led to statistical diversity.
Also, nice reading of Keith's algorithm, I was confused by the part about "carving", but now I can see from your perspective that it actually sounds right. Is Keith's algorithm on Mathworld? Maybe we could get EW to add a few more equations?
Please don't blame Fred for listening to me. We are all trying to have fun and learn more, and it doesn't hurt to double or triple check for quality assurance!
Cheers --Brad
On Wed, Aug 7, 2019 at 11:28 PM Andy Latto <andy.latto@pobox.com> wrote:
If what we're interested in is the integral of a function with respect to a particular measure, there is nothing tricky about ignoring measure zero sets. If a set has measure 0, the integral is unchanged by integrating a function that has different, arbitrary, values on that set.
Andy andy.latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
On Wed, Aug 7, 2019 at 11:39 PM Fred Lunnon <fred.lunnon@gmail.com> wrote:
However Keith's algorithm for "picking" points on a sphere does _not_ deliver uniformity -
Andy Latto<andy.latto@pobox.com> Thu, Aug 8, 2019 at 5:25 AM Yes it does.
I was a bit too casual there --- objection withdrawn and apology profferred. Yes, it _is_ a little puzzling why the von Neumann & Cook method is mentioned by Mathworld, rather than this simpler and (on reflection) obviously correct one --- which I now recall somebody else mentioned on math-fun a couple of years ago, and _still_ I didn't register it! WFL On 8/8/19, Tomas Rokicki <rokicki@gmail.com> wrote:
Here's my code, and its results.
That perimeter sure looks close to tau.
-tom
At 67108864 pts 3.99990034103394 area 2.6665184797472 perim 6.28303082552975
At 134217728 pts 3.9999551102519 area 2.66652574548337 perim 6.28309803073879
At 268435456 pts 3.99998798593879 area 2.66669666495159 perim 6.28329936437473
On Wed, Aug 7, 2019 at 9:47 PM Brad Klee <bradklee@gmail.com> wrote:
Andy,
In this case the function doesn't have poles, so you are probably right. I still think it's weird that a complete integral can be taken on an incomplete domain, so I'm willing to worry more.
Another "problem" is that, after more thought, it seems plausible that the configuration space R would need an odd volume element to match Jim Propp's preferred standard. I think it's still "okay" to start with Cartesian, but would not be surprised if this led to statistical diversity.
Also, nice reading of Keith's algorithm, I was confused by the part about "carving", but now I can see from your perspective that it actually sounds right. Is Keith's algorithm on Mathworld? Maybe we could get EW to add a few more equations?
Please don't blame Fred for listening to me. We are all trying to have fun and learn more, and it doesn't hurt to double or triple check for quality assurance!
Cheers --Brad
On Wed, Aug 7, 2019 at 11:28 PM Andy Latto <andy.latto@pobox.com> wrote:
If what we're interested in is the integral of a function with respect to a particular measure, there is nothing tricky about ignoring measure zero sets. If a set has measure 0, the integral is unchanged by integrating a function that has different, arbitrary, values on that set.
Andy andy.latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The set of k-planes planes in n-space is called the affine Grassmannian; Klain and Rota call it Graff(n,k) and construct the invariant measure on it in their book “Introduction to Geometric Probability”. I’ll write more (and respond to the questions and proposals you all have posted) in the next day or two as my time permits (I’m having an unusually busy week). Jim
And here are the final lines after an overnight run. Note that accumulating billions of doubles in this fashion loses precision; I should have done my summing more carefully. But at least five of the digits are probably good. At 8589934592 pts 4.0000236480264 area 2.66669753208071 perim 6.2832343008038 At 17179869184 pts 4.00001316709677 area 2.66668286448053 perim 6.28322083261956 At 34359738368 pts 4.00000967484084 area 2.66667855572835 perim 6.28320124178968 On Wed, Aug 7, 2019 at 10:42 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Here's my code, and its results.
That perimeter sure looks close to tau.
-tom
At 67108864 pts 3.99990034103394 area 2.6665184797472 perim 6.28303082552975
At 134217728 pts 3.9999551102519 area 2.66652574548337 perim 6.28309803073879
At 268435456 pts 3.99998798593879 area 2.66669666495159 perim 6.28329936437473
On Wed, Aug 7, 2019 at 9:47 PM Brad Klee <bradklee@gmail.com> wrote:
Andy,
In this case the function doesn't have poles, so you are probably right. I still think it's weird that a complete integral can be taken on an incomplete domain, so I'm willing to worry more.
Another "problem" is that, after more thought, it seems plausible that the configuration space R would need an odd volume element to match Jim Propp's preferred standard. I think it's still "okay" to start with Cartesian, but would not be surprised if this led to statistical diversity.
Also, nice reading of Keith's algorithm, I was confused by the part about "carving", but now I can see from your perspective that it actually sounds right. Is Keith's algorithm on Mathworld? Maybe we could get EW to add a few more equations?
Please don't blame Fred for listening to me. We are all trying to have fun and learn more, and it doesn't hurt to double or triple check for quality assurance!
Cheers --Brad
On Wed, Aug 7, 2019 at 11:28 PM Andy Latto <andy.latto@pobox.com> wrote:
If what we're interested in is the integral of a function with respect to a particular measure, there is nothing tricky about ignoring measure zero sets. If a set has measure 0, the integral is unchanged by integrating a function that has different, arbitrary, values on that set.
Andy andy.latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Very suggestive! Any stats for mean, max, min of 3/4/5-gons separately? WFL On 8/8/19, Tomas Rokicki <rokicki@gmail.com> wrote:
And here are the final lines after an overnight run. Note that accumulating billions of doubles in this fashion loses precision; I should have done my summing more carefully. But at least five of the digits are probably good.
At 8589934592 pts 4.0000236480264 area 2.66669753208071 perim 6.2832343008038
At 17179869184 pts 4.00001316709677 area 2.66668286448053 perim 6.28322083261956
At 34359738368 pts 4.00000967484084 area 2.66667855572835 perim 6.28320124178968
On Wed, Aug 7, 2019 at 10:42 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Here's my code, and its results.
That perimeter sure looks close to tau.
-tom
At 67108864 pts 3.99990034103394 area 2.6665184797472 perim 6.28303082552975
At 134217728 pts 3.9999551102519 area 2.66652574548337 perim 6.28309803073879
At 268435456 pts 3.99998798593879 area 2.66669666495159 perim 6.28329936437473
On Wed, Aug 7, 2019 at 9:47 PM Brad Klee <bradklee@gmail.com> wrote:
Andy,
In this case the function doesn't have poles, so you are probably right. I still think it's weird that a complete integral can be taken on an incomplete domain, so I'm willing to worry more.
Another "problem" is that, after more thought, it seems plausible that the configuration space R would need an odd volume element to match Jim Propp's preferred standard. I think it's still "okay" to start with Cartesian, but would not be surprised if this led to statistical diversity.
Also, nice reading of Keith's algorithm, I was confused by the part about "carving", but now I can see from your perspective that it actually sounds right. Is Keith's algorithm on Mathworld? Maybe we could get EW to add a few more equations?
Please don't blame Fred for listening to me. We are all trying to have fun and learn more, and it doesn't hurt to double or triple check for quality assurance!
Cheers --Brad
On Wed, Aug 7, 2019 at 11:28 PM Andy Latto <andy.latto@pobox.com> wrote:
If what we're interested in is the integral of a function with respect to a particular measure, there is nothing tricky about ignoring measure zero sets. If a set has measure 0, the integral is unchanged by integrating a function that has different, arbitrary, values on that set.
Andy andy.latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cool! Better still, I think I know how to prove this. That is, I think I can prove that on average a random cross-section of a unit cube has perimeter pi. More soon, Jim On Thu, Aug 8, 2019 at 10:21 AM Tomas Rokicki <rokicki@gmail.com> wrote:
And here are the final lines after an overnight run. Note that accumulating billions of doubles in this fashion loses precision; I should have done my summing more carefully. But at least five of the digits are probably good.
At 8589934592 pts 4.0000236480264 area 2.66669753208071 perim 6.2832343008038
At 17179869184 pts 4.00001316709677 area 2.66668286448053 perim 6.28322083261956
At 34359738368 pts 4.00000967484084 area 2.66667855572835 perim 6.28320124178968
I. What is the question? One can describe the measure on Graff(3,2) as follows: 1) The orientations of the planes (viewed as elements of the projective plane) are uniformly distributed relative to the measure on the projective plane that you get by taking the uniform measure on the 2-sphere and modding it out by the antipodal identification. 2) The restriction of the measure to an orientation-equivalence class of planes looks just like Lebesgue measure on the real line. This is an infinite measure, but if we restrict this measure to the subset of Graff(3,2) consisting of those planes that intersect some ball centered at the origin, we get a finite measure, which can be rescaled to yield a probability measure. Here's a concrete way to sample from that probability measure: 1) Choose a point P uniformly at random on surface of the ball and draw the line segment connecting it to its antipode P'. 2) Choose a random point Q uniformly at random from segment PP', and draw the plane through Q perpendicular to PP'. More generally, if we want to sample from those planes that intersect some compact convex body K, we can find a ball B containing K and use rejection sampling: repeatedly choose a random plane intersecting B until you find one that intersects K. There are other ways of describing the measure on Graff(3,2), and other ways to sample from it, but I like it because the rotational invariance of the measure is obvious. The same cannot be said for schemes that sample a plane ax+by+cz=d by choosing a, b, and c independently and then rejecting them if some inequality fails to hold. Anyway, this well-defined notion of a random plane that cuts a cube allows us to ask "What is the expected perimeter of a random cross-section of the unit cube?" II. Random cross-sections of a square It turns out that answering the preceding question in R^3 requires us to answer a similar question in R^2: "What is the expected length of a random cross-section of the unit square?" Here we are taking the natural measure on Graff(2,1) (the set of lines in the plane), restricting it to those lines that intersect a fixed unit square, and turning it into a probability measure. Here I will cite without proof a couple of results relating to mean width in two dimensions (I won't recite the definition of mean width since you can get that from Wikipedia). First, the mean width of a convex compact polygon A in the plane is its perimeter divided by pi; second, the average length of a random nonempty cross-section of A equals the area of A divided by the mean width of A. (For the proof of the analogous statement in three dimensions, see https://mathoverflow.net/questions/335293/mean-cross-sectional-area .) Since the unit square has perimeter 4, its mean width is 4/pi; and since its area is 1, the average length of a cross-section of the square is pi/4. Now imagine that the Euclidean 2-space E^2 that contains our unit square is actually sitting in a Euclidean 3-space E^3, and consider the subset of Graff(3,2) consisting of all planes that intersect that square. What is the expected length of the intersection of such a plane with the square? It takes a little thought to see that the answer must be the same as it is one dimension down, but it's true because of the symmetry properties of the measure on Graff(3,2). Specifically, if you look at any line in E^2 that intersects the unit square in a particular line segment, then spinning that line around the line segment gives you all the planes in E^3 that intersect the unit square in that particular segment, and the measure is rotationally uniform. (This is the only part of the argument I might have some trouble writing down formally, but I'm sure it's right.) The upshot is, if you look at a random plane that intersects a square sitting in 3-space, the expected length of the intersection is pi/4. III. Vital digression: the Wall of Fire Theorem The Wall of Fire Theorem says that the expected number of sides in a random cross-section of a cube is 4. This tells us that the probability that a random plane that intersects the cube intersects a particular face of the cube is 4/6. That's because we can write the number of sides of the cross-section as a sum of six indicator variables, one for each face of the cube, equalling 1 when random plane intersects the face in question and equalling 0 otherwise. Linearity of expectation, combined with symmetry, tells us that the expected number of sides of the intersection (which we know equals 4) must be equal to 6 times the probability that the random plane intersects a particular face of the cube. So that probability must equal 4/6, aka 2/3. IV. Random cross-sections of a hollow cube Consider a random plane that intersects a unit cube, and consider a specific face of the cube. With probability 2/3, the plane intersects the face, and conditional upon that event, the expected length of the intersection is pi/4. On the other hand, with probability 1/3, the plane doesn't intersect the face, and conditional upon that event, the expected length of the intersection is 0. So the unconditioned expectation of the length of that intersection is equal to (2/3)(pi/4) + (1/3)(0) = pi/6. Lastly, if we sum over all the faces of the cube, we find that the expected length of the intersection between the random plane and the surface of the cube is (6)(pi/6) = pi. So this is indeed the expected perimeter of a random cross-section of the unit cube. V. Random cross-sectional area To prove that a random cross-section of the unit cube has area 2/3, one can appeal to the MathOverflow post I cited before, showing that the average cross-sectional area of a convex compact body in 3-space equals the volume divided by the mean width, and the fact that a cube of side-length s has mean width 3/2. I know of a nice way to prove the latter fact by way of Archimedes' hat-box theorem, but this email has gone for way too long already.) To recap: a random cross-section of the unit cube has 4 sides, has area 2/3, and has perimeter pi. I think that's swell. Thanks for helping me figure this out! Jim Propp On Thu, Aug 8, 2019 at 6:27 PM James Propp <jamespropp@gmail.com> wrote:
Cool!
Better still, I think I know how to prove this. That is, I think I can prove that on average a random cross-section of a unit cube has perimeter pi.
More soon,
Jim
On Thu, Aug 8, 2019 at 10:21 AM Tomas Rokicki <rokicki@gmail.com> wrote:
And here are the final lines after an overnight run. Note that accumulating billions of doubles in this fashion loses precision; I should have done my summing more carefully. But at least five of the digits are probably good.
At 8589934592 pts 4.0000236480264 area 2.66669753208071 perim 6.2832343008038
At 17179869184 pts 4.00001316709677 area 2.66668286448053 perim 6.28322083261956
At 34359738368 pts 4.00000967484084 area 2.66667855572835 perim 6.28320124178968
For anyone still following the random-cross-sections-of-a-cube saga, I should mention that I've finally reopened my copy of Klain and Rota's "Introduction to Geometric Probability" (after a decade-long hiatus) and checked that Crofton's formula (Theorem 9.3.2) confirms that a random nonempty cross-section of a cube has area 2/3 and perimeter pi on average. However, I don't know of any variant of Crofton's formula that would compute the expected number of vertices of the intersection. Klain and Rota don't go into that sort of thing because they're concerned with valuations, and the "count-the-corners" map from convex polygons to integers isn't additive the way area and perimeter are. If any of you know of variants of Crofton's formula and/or the kinematic formula that apply to those more general sorts of questions, please let me know! Jim Propp On Thu, Aug 8, 2019 at 7:41 PM James Propp <jamespropp@gmail.com> wrote:
I. What is the question?
One can describe the measure on Graff(3,2) as follows:
1) The orientations of the planes (viewed as elements of the projective plane)
are uniformly distributed relative to the measure on the projective plane that
you get by taking the uniform measure on the 2-sphere and modding it out by
the antipodal identification.
2) The restriction of the measure to an orientation-equivalence class of
planes looks just like Lebesgue measure on the real line.
This is an infinite measure, but if we restrict this measure to the subset of
Graff(3,2) consisting of those planes that intersect some ball centered at the
origin, we get a finite measure, which can be rescaled to yield a probability
measure. Here's a concrete way to sample from that probability measure:
1) Choose a point P uniformly at random on surface of the ball and draw the
line segment connecting it to its antipode P'.
2) Choose a random point Q uniformly at random from segment PP', and draw
the plane through Q perpendicular to PP'.
More generally, if we want to sample from those planes that intersect some
compact convex body K, we can find a ball B containing K and use rejection
sampling: repeatedly choose a random plane intersecting B until you find one
that intersects K.
There are other ways of describing the measure on Graff(3,2), and other ways
to sample from it, but I like it because the rotational invariance of the
measure is obvious. The same cannot be said for schemes that sample a plane
ax+by+cz=d by choosing a, b, and c independently and then rejecting them
if some inequality fails to hold.
Anyway, this well-defined notion of a random plane that cuts a cube allows
us to ask "What is the expected perimeter of a random cross-section of the
unit cube?"
II. Random cross-sections of a square
It turns out that answering the preceding question in R^3 requires us to
answer a similar question in R^2: "What is the expected length of a random
cross-section of the unit square?" Here we are taking the natural measure
on Graff(2,1) (the set of lines in the plane), restricting it to those
lines that intersect a fixed unit square, and turning it into a probability
measure.
Here I will cite without proof a couple of results relating to mean width
in two dimensions (I won't recite the definition of mean width since you
can get that from Wikipedia). First, the mean width of a convex compact polygon
A in the plane is its perimeter divided by pi; second, the average length of
a random nonempty cross-section of A equals the area of A divided by the mean
width of A. (For the proof of the analogous statement in three dimensions,
see https://mathoverflow.net/questions/335293/mean-cross-sectional-area .)
Since the unit square has perimeter 4, its mean width is 4/pi; and since its
area is 1, the average length of a cross-section of the square is pi/4.
Now imagine that the Euclidean 2-space E^2 that contains our unit square
is actually sitting in a Euclidean 3-space E^3, and consider the subset of
Graff(3,2) consisting of all planes that intersect that square. What is the
expected length of the intersection of such a plane with the square? It takes
a little thought to see that the answer must be the same as it is one dimension
down, but it's true because of the symmetry properties of the measure on
Graff(3,2). Specifically, if you look at any line in E^2 that intersects
the unit square in a particular line segment, then spinning that line around
the line segment gives you all the planes in E^3 that intersect the unit square
in that particular segment, and the measure is rotationally uniform. (This
is the only part of the argument I might have some trouble writing down
formally, but I'm sure it's right.)
The upshot is, if you look at a random plane that intersects a square sitting
in 3-space, the expected length of the intersection is pi/4.
III. Vital digression: the Wall of Fire Theorem
The Wall of Fire Theorem says that the expected number of sides in a random
cross-section of a cube is 4. This tells us that the probability that a random
plane that intersects the cube intersects a particular face of the cube is
4/6. That's because we can write the number of sides of the cross-section as
a sum of six indicator variables, one for each face of the cube, equalling 1
when random plane intersects the face in question and equalling 0 otherwise.
Linearity of expectation, combined with symmetry, tells us that the expected
number of sides of the intersection (which we know equals 4) must be equal to
6 times the probability that the random plane intersects a particular face of
the cube. So that probability must equal 4/6, aka 2/3.
IV. Random cross-sections of a hollow cube
Consider a random plane that intersects a unit cube, and consider a specific
face of the cube. With probability 2/3, the plane intersects the face, and
conditional upon that event, the expected length of the intersection is pi/4.
On the other hand, with probability 1/3, the plane doesn't intersect the face,
and conditional upon that event, the expected length of the intersection is 0.
So the unconditioned expectation of the length of that intersection is equal to
(2/3)(pi/4) + (1/3)(0) = pi/6.
Lastly, if we sum over all the faces of the cube, we find that the expected
length of the intersection between the random plane and the surface of the
cube is (6)(pi/6) = pi. So this is indeed the expected perimeter of a random
cross-section of the unit cube.
V. Random cross-sectional area
To prove that a random cross-section of the unit cube has area 2/3, one can
appeal to the MathOverflow post I cited before, showing that the average
cross-sectional area of a convex compact body in 3-space equals the volume
divided by the mean width, and the fact that a cube of side-length s has
mean width 3/2. I know of a nice way to prove the latter fact by way of
Archimedes' hat-box theorem, but this email has gone for way too long already.)
To recap: a random cross-section of the unit cube has 4 sides, has area 2/3,
and has perimeter pi. I think that's swell. Thanks for helping me figure
this out!
Jim Propp
On Thu, Aug 8, 2019 at 6:27 PM James Propp <jamespropp@gmail.com> wrote:
Cool!
Better still, I think I know how to prove this. That is, I think I can prove that on average a random cross-section of a unit cube has perimeter pi.
More soon,
Jim
On Thu, Aug 8, 2019 at 10:21 AM Tomas Rokicki <rokicki@gmail.com> wrote:
And here are the final lines after an overnight run. Note that accumulating billions of doubles in this fashion loses precision; I should have done my summing more carefully. But at least five of the digits are probably good.
At 8589934592 pts 4.0000236480264 area 2.66669753208071 perim 6.2832343008038
At 17179869184 pts 4.00001316709677 area 2.66668286448053 perim 6.28322083261956
At 34359738368 pts 4.00000967484084 area 2.66667855572835 perim 6.28320124178968
For Mma implementation, see also: https://0x0.st/zOdi.txt . I only ran to 100k, but the output agrees with Tom R. Woohoo! We have almost calculated 2*Pi again! What a great number! But how about the 3x1x3 volume? Integration over this domain produces a result likely different by ten to fifteen percent. So does anyone know how to write the volume element to recover standard measure? Is it just the determinant of a Jacobian matrix? If yes, what is this matrix? --Brad On Thu, Aug 8, 2019 at 12:43 AM Tomas Rokicki <rokicki@gmail.com> wrote:
Here's my code, and its results.
On Thu, Aug 8, 2019, 00:47 Brad Klee <bradklee@gmail.com> wrote:
Andy,
In this case the function doesn't have poles, so you are probably right.
It makes no difference whether the function has poles or not. If the aLebesgie integral exists ( which requires the function to be defined and finite except possibly on a set of measure zero, then changing the function on a set of measure zero does not change the integral.
I still think it's weird that a complete integral can be taken on an incomplete domain, so I'm willing to worry more.
The definition of Lebesgue integration is a fairly fundamental part of analysis. What about it worries you? Andy
Another "problem" is that, after more thought, it seems plausible that the configuration space R would need an odd volume element to match Jim Propp's preferred standard. I think it's still "okay" to start with Cartesian, but would not be surprised if this led to statistical diversity.
Also, nice reading of Keith's algorithm, I was confused by the part about "carving", but now I can see from your perspective that it actually sounds right. Is Keith's algorithm on Mathworld? Maybe we could get EW to add a few more equations?
Please don't blame Fred for listening to me. We are all trying to have fun and learn more, and it doesn't hurt to double or triple check for quality assurance!
Cheers --Brad
On Wed, Aug 7, 2019 at 11:28 PM Andy Latto <andy.latto@pobox.com> wrote:
If what we're interested in is the integral of a function with respect to a particular measure, there is nothing tricky about ignoring measure zero sets. If a set has measure 0, the integral is unchanged by integrating a function that has different, arbitrary, values on that set.
Andy andy.latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Lebesgue Commandment: Ignore all measure zero sets. Numerical Recipe: Only calculate measure zero sets. In the other thread, we are talking about computational practice, so I'm spinning this response another direction. See also the other thread "Loosing sleep because..." : https://mailman.xmission.com/cgi-bin/mailman/private/math-fun/2019-August/03... Instead of "0*Infinity = 0", perhaps it should be card(Z)*(1/card(R))=0. Then what if the function is allowed to take on a value f(0)=card(R)? Is it still okay to ignore the one-point set at t=0? You're welcome to keep up the antagonism, but please try not to make me look like too much of an idiot. Thanks --Brad On Fri, Aug 9, 2019 at 8:24 PM Andy Latto <andy.latto@pobox.com> wrote:
The definition of Lebesgue integration is a fairly fundamental part of analysis. What about it worries you? Andy
A function f satisfying f(0)=card(R) isn’t the sort of function treated in any flavor of real analysis I’ve seen, because card(R) is a cardinal, not a real number. I expect that it would be hard to create an extension of real analysis that would treat such things in a consistent and interesting way. The closest thing to what Brad is imagining (that I’m aware of) is surreal analysis, which is fraught with difficulty. Jim Propp On Tue, Aug 13, 2019 at 12:52 PM Brad Klee <bradklee@gmail.com> wrote:
Lebesgue Commandment: Ignore all measure zero sets. Numerical Recipe: Only calculate measure zero sets.
In the other thread, we are talking about computational practice, so I'm spinning this response another direction. See also the other thread "Loosing sleep because..." :
https://mailman.xmission.com/cgi-bin/mailman/private/math-fun/2019-August/03...
Instead of "0*Infinity = 0", perhaps it should be card(Z)*(1/card(R))=0. Then what if the function is allowed to take on a value f(0)=card(R)? Is it still okay to ignore the one-point set at t=0?
You're welcome to keep up the antagonism, but please try not to make me look like too much of an idiot.
Thanks --Brad
On Fri, Aug 9, 2019 at 8:24 PM Andy Latto <andy.latto@pobox.com> wrote:
The definition of Lebesgue integration is a fairly fundamental part of analysis. What about it worries you? Andy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Keith, A quick way to debug this. Keep track of the highest area seen so far and every time you see a new high area print out the points. The highest area I'm seeing is 4 sqrt(2) or about 5.656, but you report a high area of 6.9. My guess is something is wrong with your sorting of points, and this is affecting your area calculation. Quick question for the math fun crowd: is there a slice of a cube (any orientation) with an area greater than 4 sqrt 2? Or is my program buggy? -tom On Tue, Aug 6, 2019 at 7:40 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Sorry it took me a while to finish my program that finds the average perimeters and areas of the intersection of a plane with a cube.
On July 28th, I wrote:
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong.
This got me the correct perimeter length. Correct as supported by the program's agreeing with Fred Lunnon's and my ideas of what the smallest and largest perimeters should be for each n-gon.
Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries.
Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others already in the table. So for the largest possible n, 6, 60 tries.
On July 29th I wrote:
Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together.
This should have worked. I spent most of my time trying, without success, to figure out why it didn't work. I knew it wasn't working because I was getting impossibly large areas. (Except for triangles, where it appeared to be correct, given the maximum area it found.) I was hampered in debugging by the fact that I have no way of generating graphics. All I have to look at are lists of numbers. And I'm not a visual thinker, anyway.
Eventually, I figured it must be that I was somehow mistaken that the sequence of vertices with the smallest sum of successive distances was the actual perimeter. I couldn't visualize how that could possibly be, but visualization isn't my strong suit. Yes, the perimeter maxima were correct, but that's no surprise given that a hypothetical incorrect vertex order with a smaller distance sum wouldn't affect that maximum.
I looked forward to finding an exception, then drawing it by hand. So I implemented a variant of James Propp's suggestion that I rotate the polygon into the x,y plane, then convert from rectangular to polar coordinates, with the centroid as the origin, and sort by theta. Since at that time I only cared about the order of vertices, I instead simply discarded the z coordinate rather than doing a 3D rotation. (I am perhaps irrationally prejudiced against unnecessary trigonometry, as I'm under the perhaps outdated impression that trig makes programs very slow.)
Much to my surprise, I discovered that the orders were the same. (At least for all of ten million random planes.) The flaw in my area algorithm was elsewhere. I continued looking for it until I started running out of time. (James Propp's talk is on August 7th, and today is the 6th.) Then I tried getting the area from my projection into the x,y plane, using the shoelace formula (which was suggested by both James Propp and Tom Duff). The projection is obviously going to be foreshortened, so I tried multiplying it by the slope of the original polygon to fix it. Apparently I computed the slope wrong, as the areas of triangles (hence presumably also all other figures) were wrong.
Fortunately, Tom Duff also said, "In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares." Since it was easy to adapt my code which projected into the x,y plane and worked there into doing the same with the other two orthogonal planes, so I did it that way.
Then I had a tenacious bug that was due to the modulo function in C being broken. -1 mod 3 should be 2, not -1.
Once I changed
at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3]));
to
j1 = (j-1)%g; if (j1 < 0) j1 += g; at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3]));
it started working perfectly.
(That's the shoelace formula.)
In retrospect I should have documented better, used more meaningful variable names, and unrolled those nested subscripts. But the program started two years ago as a quick and dirty hack to measure the average number of edges of the intersection polygon, so I used "alpine programming," by analogy with "alpine style mountain climbing," which means not bothering with those tedious base camps and pre-positioning supplies, but instead just racing for the summit. In my defense, mountains, unlike programming tasks, seldom suddenly get much taller.
Anyhow, without further ado, here are the results, based on the average of two runs of a billion random planes. Again, the cube's side length is 2.
Smallest, average, and largest perimeters: 3 sides: 0.0000 3.0613 8.4736 4 sides: 4.0001 7.1700 9.6550 5 sides: 6.8314 8.2032 9.6521 6 sides: 8.4853 8.6827 9.6511
All over average perimeter: 6.2841
Smallest, average, and largest areas: 3 sides: 0.0000 0.5496 3.4546 4 sides: 0.0001 3.2519 6.9252 5 sides: 3.0088 4.6743 6.9218 6 sides: 5.1975 5.8310 6.9240
All over average area: 2.8819
Proportion of each polygon type: 3 sides: 27.97% 4 sides: 48.68% 5 sides: 18.70% 6 sides: 4.65%
I'm CCing James Propp so that he'll get this in time for tomorrow's talk even if he's on the digest option and no digest goes out before that talk.
Tomorrow I'll return to trying to figure out why my original area formula isn't working.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
<< Quick question for the math fun crowd: is there a slice of a cube (any orientation) with an area greater than 4 sqrt 2? >> I can very nearly confirm there are none --- but not quite! The closure of pentagonal cross-sections includes all maximal-area quadrilateral and triangular ones; and their overall area supremum equals 4 sqrt 2 , as proposed by Tomas. I have yet to consider hexagons: though Keith's data do suggest that their supremum is no different. Incidentally, regarding minima: all trivially 0 for triangular and quadrilateral; for pentagonal cross-sections, I now have Triangular perimeter infimum at plane = [-1, 0, 0, 1] ; perimeter = 4 + 2 sqrt(2) ~ 6.82842712 ; vertices = [1,-1,+1,+1], [1,+1,-1,+1], [1,+1,+1,+1] ; Fred Lunnon On 8/8/19, Tomas Rokicki <rokicki@gmail.com> wrote:
Keith,
A quick way to debug this. Keep track of the highest area seen so far and every time you see a new high area print out the points.
The highest area I'm seeing is 4 sqrt(2) or about 5.656, but you report a high area of 6.9. My guess is something is wrong with your sorting of points, and this is affecting your area calculation.
Quick question for the math fun crowd: is there a slice of a cube (any orientation) with an area greater than 4 sqrt 2?
Or is my program buggy?
-tom
On Tue, Aug 6, 2019 at 7:40 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Sorry it took me a while to finish my program that finds the average perimeters and areas of the intersection of a plane with a cube.
On July 28th, I wrote:
Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong.
This got me the correct perimeter length. Correct as supported by the program's agreeing with Fred Lunnon's and my ideas of what the smallest and largest perimeters should be for each n-gon.
Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries.
Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others already in the table. So for the largest possible n, 6, 60 tries.
On July 29th I wrote:
Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together.
This should have worked. I spent most of my time trying, without success, to figure out why it didn't work. I knew it wasn't working because I was getting impossibly large areas. (Except for triangles, where it appeared to be correct, given the maximum area it found.) I was hampered in debugging by the fact that I have no way of generating graphics. All I have to look at are lists of numbers. And I'm not a visual thinker, anyway.
Eventually, I figured it must be that I was somehow mistaken that the sequence of vertices with the smallest sum of successive distances was the actual perimeter. I couldn't visualize how that could possibly be, but visualization isn't my strong suit. Yes, the perimeter maxima were correct, but that's no surprise given that a hypothetical incorrect vertex order with a smaller distance sum wouldn't affect that maximum.
I looked forward to finding an exception, then drawing it by hand. So I implemented a variant of James Propp's suggestion that I rotate the polygon into the x,y plane, then convert from rectangular to polar coordinates, with the centroid as the origin, and sort by theta. Since at that time I only cared about the order of vertices, I instead simply discarded the z coordinate rather than doing a 3D rotation. (I am perhaps irrationally prejudiced against unnecessary trigonometry, as I'm under the perhaps outdated impression that trig makes programs very slow.)
Much to my surprise, I discovered that the orders were the same. (At least for all of ten million random planes.) The flaw in my area algorithm was elsewhere. I continued looking for it until I started running out of time. (James Propp's talk is on August 7th, and today is the 6th.) Then I tried getting the area from my projection into the x,y plane, using the shoelace formula (which was suggested by both James Propp and Tom Duff). The projection is obviously going to be foreshortened, so I tried multiplying it by the slope of the original polygon to fix it. Apparently I computed the slope wrong, as the areas of triangles (hence presumably also all other figures) were wrong.
Fortunately, Tom Duff also said, "In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares." Since it was easy to adapt my code which projected into the x,y plane and worked there into doing the same with the other two orthogonal planes, so I did it that way.
Then I had a tenacious bug that was due to the modulo function in C being broken. -1 mod 3 should be 2, not -1.
Once I changed
at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3]));
to
j1 = (j-1)%g; if (j1 < 0) j1 += g; at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3]));
it started working perfectly.
(That's the shoelace formula.)
In retrospect I should have documented better, used more meaningful variable names, and unrolled those nested subscripts. But the program started two years ago as a quick and dirty hack to measure the average number of edges of the intersection polygon, so I used "alpine programming," by analogy with "alpine style mountain climbing," which means not bothering with those tedious base camps and pre-positioning supplies, but instead just racing for the summit. In my defense, mountains, unlike programming tasks, seldom suddenly get much taller.
Anyhow, without further ado, here are the results, based on the average of two runs of a billion random planes. Again, the cube's side length is 2.
Smallest, average, and largest perimeters: 3 sides: 0.0000 3.0613 8.4736 4 sides: 4.0001 7.1700 9.6550 5 sides: 6.8314 8.2032 9.6521 6 sides: 8.4853 8.6827 9.6511
All over average perimeter: 6.2841
Smallest, average, and largest areas: 3 sides: 0.0000 0.5496 3.4546 4 sides: 0.0001 3.2519 6.9252 5 sides: 3.0088 4.6743 6.9218 6 sides: 5.1975 5.8310 6.9240
All over average area: 2.8819
Proportion of each polygon type: 3 sides: 27.97% 4 sides: 48.68% 5 sides: 18.70% 6 sides: 4.65%
I'm CCing James Propp so that he'll get this in time for tomorrow's talk even if he's on the digest option and no digest goes out before that talk.
Tomorrow I'll return to trying to figure out why my original area formula isn't working.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (8)
-
Allan Wechsler -
Andy Latto -
Brad Klee -
bradklee＠gmail.com
-
Fred Lunnon -
James Propp -
Keith F. Lynch -
Tomas Rokicki