<< 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