# Biggest Little Polyhedra

Posted 4 years ago
19624 Views
|
26 Replies
|
50 Total Likes
|
 The biggest little polygon is the n-gon with maximum diameter 1 that has the greatest volume.I've often wondered the same problem about polyhedra, and posted a biggest little polyhedron question on StackExchange, where it got no answers. Mathematica 10 has Volume[] and ConvexHullMesh[]. Calculating the volume of the convex hull of 20 random points is as simple as Volume[ConvexHullMesh[RandomReal[{-1, 1}, {20, 3}]]] so I decided to solve the problem myself. First, I used some code like the below to find the solution randomly, with a bit of anealling. numpts = 5; maxvol = .05; count = 0; div = 1; pts = RandomReal[{-1, 1}, {numpts, 3}]; Monitor[Do[ kk = RandomReal[{-1, 1}, {numpts, 3}]/div + pts; maxlen = Max[EuclideanDistance[#[[1]], #[[2]]] & /@ Subsets[kk, {2}]]; vol = Volume[ConvexHullMesh[kk/maxlen]]; If[vol > maxvol, count = 0; maxvol = vol; pts = kk/maxlen, count = count + 1]; If[count > 1000, count = 0; div = 1.3 div; Print[{maxvol, pts}]], {gg, 1, 100000}], {count, maxvol, pts}] The best solution for 4 points is the regular tetrahedron with edge lengths 1. The best solutions I could find for 5 through 12 points were considerably stranger. Red lines indicate a distance of 1. Volumes appear underneath.Most of these solutions could doubtlessly be improved or made more exact. If anyone can provide any improvements, please post them. Attachments:
26 Replies
Sort By:
Posted 4 years ago
 Really cool Ed.How does the 5 pointer compare with the square pyramid? The one you have here looks similar and the volume seems similar too.
Posted 4 years ago
 Ok, to answer my own question the square pyramid is a little better. p5 = {{0, 0, 0}, {0, 1, 0}/Sqrt[2], {1, 1, 0}/Sqrt[2], {1/Sqrt[2], 0, 0}, {1/(2 Sqrt[2]), 1/(2 Sqrt[2]), Sqrt[3]/2}}; Volume[Pyramid[p5]] (* 1/(4 Sqrt[3]) *) However the difference in volume is like 7*10^-6 and the numerical result has a few diagonals which could be stretched a little further to be length 1. Not sure what sort of simple code can adjust that.If the square pyramid is optimal it would be a nice example of having 5 equal basins in this space of 5 pointed polyhedral..On the other hand, the cube has 8 points, and for the long diagonal to be length one, the sides have to be 1/Sqrt[3] with a volume of less than .2, then Ed's result with randomized improvement is much better. I'm curious if there is a NKS approach, especially since this is the season for applications to the Wolfram Science Summer School.From a math point of view, I wonder about frameworks to prove results about big little polyhedral.
Posted 4 years ago
 Yes, we can settle p5. p5a = {{1/2, 0, 0}, {-1/2, 0, 0}, {0, Sqrt[3]/2, 0}, {0, Sqrt[3]/6, 1/2}, {0, Sqrt[3]/6, -1/2}}; p5b = {{0, 0, 0}, {0, 1, 0}/Sqrt[2], {1, 1, 0}/Sqrt[2], {1/Sqrt[2], 0,0}, {1/(2 Sqrt[2]), 1/(2 Sqrt[2]), Sqrt[3]/2}}; Row[Graphics3D[{{Red, Line /@ Select[Subsets[#, {2}], EuclideanDistance[#[[1]], #[[2]]] > .999 &]}, Opacity[.5], ConvexHullMesh[#]["GraphicsComplex"]}, Boxed -> False, SphericalRegion -> True, ViewAngle -> Pi/8, ImageSize -> {300, 300}] & /@ {p5a, p5b}] Both with volume Sqrt[3]/12 == 0.14433756729740644113 With five points, three of the points will make an equilateral triangle. Make that the base plane. If the other two points are perpendicular to the plane and a distance of 1 apart, then the maximum volume is reached. There are thus infinite solutions for the five point case.
Posted 4 years ago
 I believe I've solved 6 points. p6 = {{1/2,0,0}, {-(1/2),0,0}, {0,Root[-27+576 #1^2+84 #1^4+688 #1^6-448 #1^8-512 #1^10+256 #1^12&,4],-(1/2)}, {0,Root[-27-540 #1^2+3780 #1^4-896 #1^6-9728 #1^8-4096 #1^10+16384 #1^12&,6], Root[-27-108 #1+84 #1^2+448 #1^3-256 #1^4-384 #1^5+256 #1^6&,3]}, {0,Root[-27-540 #1^2+3780 #1^4-896 #1^6-9728 #1^8-4096 #1^10+16384 #1^12&,6], Root[-27+108 #1+84 #1^2-448 #1^3-256 #1^4+384 #1^5+256 #1^6&,2]}, {0,Root[-27+576 #1^2+84 #1^4+688 #1^6-448 #1^8-512 #1^10+256 #1^12&,4],1/2}}; vol = Root[-187489+45488880 #1^2-1413391680 #1^4+4196745216 #1^6+256714997760 #1^8-4109478395904 #1^10+21134460321792 #1^12&,5]; N[vol,50] Graphics3D[{{Red, Tube/@ Select[Subsets[best, {2}], EuclideanDistance[#[[1]], #[[2]]] > .999 &]}, Opacity[.5], ConvexHullMesh[best]["GraphicsComplex"]}, Boxed -> False, SphericalRegion -> True, ViewAngle -> Pi/8, ImageSize -> {400, 400}] max volume is 0.19540886771205179257545855426296510206490511442893... Here's an image, with the points {1/2,0,0}, {-(1/2),0,0} making the diagonal at the top.
Posted 4 years ago
 I believe the best volume for p7 is 0.22845063813064674774720321520495348848601269300611..., which is the root object Root[-1514051 + 3577325760 #1^2 - 2684555965440 #1^4 + 625333560016896 #1^6 + 37285432786944 #1^8 + 181475831829233664 #1^10 - 16291819718669500416 #1^12 + 160710642044510404608 #1^14 + 134780624734481547264 #1^16 &, 9] Refinement of the originally found p7 object suggested order-3 symmetry, and further refinement suggested that the necessary figure used the following points, for some .4 < r < .6. {{0,1/Sqrt[3],0}, {1/2,-(1/(2 Sqrt[3])),0}, {-(1/2),-(1/(2 Sqrt[3])),0}, {0,-(r/Sqrt[3]),Sqrt[2-r (2+r)]/Sqrt[3]}, {-(r/2), r/(2 Sqrt[3]), Sqrt[2-r (2+r)]/Sqrt[3]}, {r/2,r/(2 Sqrt[3]),Sqrt[2-r (2+r)]/Sqrt[3]}, {0,0,(-Sqrt[3-r^2]+Sqrt[2-r (2+r)])/Sqrt[3]}} This can be split into 7 tetrahedra with a simple-looking volume formula, but the actual maximum is that ugly root object above. Maximize[1/12 (Sqrt[3 - r^2] + r (2 + r) Sqrt[2 - r (2 + r)]), r] r turns out to be Root[-16+16 #1+74 #1^2-18 #1^3-116 #1^4-50 #1^5+22 #1^6+18 #1^7+3 #1^8&,4] . p7 =RootReduce[With[{r = Root[-16+16 #1+74 #1^2-18 #1^3-116 #1^4-50 #1^5+22 #1^6+18 #1^7+3 #1^8&,4]}, {{0,1/Sqrt[3],0},{1/2,-(1/(2 Sqrt[3])),0},{-(1/2),-(1/(2 Sqrt[3])),0},{0,-(r/Sqrt[3]),Sqrt[2-r (2+r)]/Sqrt[3]}, {-(r/2),r/(2 Sqrt[3]),Sqrt[2-r (2+r)]/Sqrt[3]},{r/2,r/(2 Sqrt[3]),Sqrt[2-r (2+r)]/Sqrt[3]},{0,0,(-Sqrt[3-r^2]+Sqrt[2-r (2+r)])/Sqrt[3]}}]]; Graphics3D[{{Red, Tube /@ Select[Subsets[p7, {2}], EuclideanDistance[#[[1]], #[[2]]] > .999 &]}, Opacity[.7], ConvexHullMesh[p7]["GraphicsComplex"]}, Boxed -> False, SphericalRegion -> True, ViewAngle -> Pi/8, ImageSize -> {500, 500}] Giving a solution that looks like the following:
Posted 4 years ago
 Awesome. Not sure if I will be able to sleep tonight.
Posted 4 years ago
 To optimize p8, with a volume somewhere around 0.27100523, I'll need to split the following into discrete tetrahedra and use a tetrahedron volume formula to get the exact equation based on p. p8rep = {{1/2,0,1/2 (-2 p+Sqrt[1+8 p^2-2 Sqrt[2-8 p^2]])}, {-1/2,0,1/2 (-2 p+Sqrt[1+8 p^2-2 Sqrt[2-8 p^2]])},{0,1/2,-(1/2 (-2 p+Sqrt[1+8 p^2-2 Sqrt[2-8 p^2]]))}, {0,-1/2,-(1/2 (-2 p+Sqrt[1+8 p^2-2 Sqrt[2-8 p^2]]))}, {0,Sqrt[1/2-2 p^2],p},{0,-Sqrt[1/2-2 p^2],p}, {Sqrt[1/2-2 p^2],0,-p},{-Sqrt[1/2-2 p^2],0,-p}}; p8 = p8rep/.p->0.450373121; Graphics3D[{{Red, Tube /@ Select[Subsets[p8, {2}], EuclideanDistance[#[[1]], #[[2]]] > .999 &]}, Opacity[.5], ConvexHullMesh[p8]["GraphicsComplex"]}, Boxed -> False, SphericalRegion -> True, ViewAngle -> Pi/9, ImageSize -> {500, 500}] Volume[ConvexHullMesh[p8]] Here's a few views of this polyhedron. Breaking it down into tetrahedra wasn't hard. By symmetry, needed 2 each of 5 tetrahedra and one of another. When using the tetrahedron volume formula, make sure all the volumes are positive, switching two numbers if necessary. p8mat = Append[#,1]&/@p8rep;p8vol = FullSimplify[(Total[(2 Det[#] & /@ ((p8mat[[#]] & /@ #) & /@ {{2, 5, 3, 8}, {4, 6, 2, 8} , {2, 5, 8, 6} , {3, 6, 4, 8}, {3, 6, 8, 5}}))] + Det[p8mat[[{4, 3, 8, 7}]]])/6];RootReduce /@ Maximize[1/6 (2 p + Sqrt[2 - 8 p^2] Sqrt[1 + 8 p^2 - 2 Sqrt[2 - 8 p^2]]), p] Giving the p value that gives the maximum volume. {Root[-3170503 + 7784640504 #1^2 - 86041951920 #1^4 - 775194852096 #1^6 + 8843870241792 #1^8 - 28203359404032 #1^10 + 35664401793024 #1^12 &, 5], {p -> Root[-7 - 584 #1^2 + 27728 #1^4 - 129792 #1^6 - 424960 #1^8 + 1441792 #1^10 + 4194304 #1^12 &, 6]}} That volume is 0.27100523096446955933460701009076408686501941033169... , for p = 0.4503731221464994772... I love that Mathematica can crank out exact answers for these.
Posted 4 years ago
 For higher order n, solutions of the Thomson problem, which minimize a point charge on a sphere, tend to give poor solutions because there are a lot of poles which go through the center of the sphere. In a BiggestLittlePolyhedron solution, likely no poles go through the center.Adapting Thomson code so that points repel both points and their polar opposites would likely yield good starting points for BiggestLittlePolyhedron solutions.
Posted 4 years ago
 It seems that optimal solutions for 5 and 6 points are in the literature. The published solutions seem to match yours.For five points: Bernd Kind, Peter Kleinschmidt, On the maximal volume of convex bodies with few vertices, Journal of Combinatorial Theory, Series A, Volume 21, Issue 1, July 1976, Pages 124–128, doi:10.1016/0097-3165(76)90056-X.For six points: Andreas Klein, Markus Wessler, The largest small n-dimensional polytope with n+3 vertices, Journal of Combinatorial Theory, Series A, Volume 102, Issue 2, May 2003, Pages 401–409, doi:10.1016/S0097-3165(03)00054-2.There is an error in the latter paper, but the three-dimensional case survives it: Andreas Klein, Markus Wessler, A correction to “The largest small n-dimensional polytope with vertices”, Journal of Combinatorial Theory, Series A, Volume 112, Issue 1, October 2005, Pages 173–174, doi:10.1016/j.jcta.2005.06.001.
Posted 4 years ago
 For 9 points, the volume is Root[177957 - 2343420 #1^2 + 6129856 #1^4 - 3704832 #1^6 + 746496 #1^8 &, 3], which equals 0.31788630328234374954985598246259310693700354458983 The best of the randomly optimized objects was heading towards this structure, for a~.37 p9rep = {a {0, 1, Sqrt[1 - 3 a^2]/(2 a)}, a {Sqrt[3]/2, -(1/2), Sqrt[1 - 3 a^2]/(2 a)}, a {-(Sqrt[3]/2), -(1/2), Sqrt[1 - 3 a^2]/( 2 a)}, (-a + 1/2 Sqrt[3] Sqrt[1 + a^2]) {0, -1, 0}, (-a + 1/2 Sqrt[3] Sqrt[1 + a^2]) {-(Sqrt[3]/2), 1/2, 0}, (-a + 1/2 Sqrt[3] Sqrt[1 + a^2]) {Sqrt[3]/2, 1/2, 0}, a {0, 1, -(Sqrt[1 - 3 a^2]/(2 a))}, a {Sqrt[3]/2, -(1/2), -(Sqrt[1 - 3 a^2]/(2 a))}, a {-(Sqrt[3]/2), -(1/2), -(Sqrt[1 - 3 a^2]/(2 a))}}; The figure has 3 pyramids and a prism, leading to a volume with an equation that can be solved like so. RootReduce[a /. Solve[D[3/4 Sqrt[1 - 3 a^2] (Sqrt[3] a^2 + 2 Sqrt[a^2] Sqrt[1 + 4 a^2 - 2 Sqrt[3] a Sqrt[1 + a^2]]), a] == 0][1]] That yields a = Root[4 - 44 #1^2 + 88 #1^4 + 153 #1^6 + 81 #1^8 &, 3] = 0.37644709752527680475 , which can be plugged into the volume equation to give the root object at the start of the post.
Posted 4 years ago
 I believe I've solved 10 and 16. My other results from 11 to 24 are all fragile, and my computer runs frequently improve them. I'm working on a blog for all this, but I'd like to get more solid results. So, I'm tossing things out to the Community. Here are my best known results so far. 4 . 0.117851 ... ..9 . 0.317886 ... 14 . 0.380268 ... 19 . 0.4191755 . 0.144338 ... 10 . 0.332531 ... 15 . 0.389714 ... 20 . 0.4232706 . 0.195409 ... 11 . 0.343976 ... 16 . 0.405805 ... 21 . 0.4283477 . 0.228451 ... 12 . 0.356288 ... 17 . 0.409869 ... 22 . 0.4307278 . 0.271005 ... 13 . 0.367105 ... 18 . 0.415037 ... 23 . 0.434854 If you'd like to help to try to improve things, download the attached notebook, change the file path, and then run some variation of the code under "Try to get better results". If it prints out something, post the best results for each number here, along with your name. Take a look here first to see if someone already has posted a better result. I'll try to keep this status page and the notebook updated.If your result is the best, I'll mention your name in the write-up. Attachments:
Posted 4 years ago
 Trimmed this message away, really old results.
Posted 4 years ago
 As it looks to me, the most obvious strategy was not tried so far: Take a sphere of diameter 1 and place all your trial points on it (i.e. on the surface of a globe). ( Notice that for the 2-dimensional problem and the regular n-gons the corresponding strategy works.) Set up a simple dynamical system that lets the points move along the surface under forces for mutual repulsion and friction with respect to the surface. If you use a stable integrator such as Störmer-Verlet the points will arrange themselves very fast into a configuration where points are at rest and the potential energy of repulsion takes a minimum. (My personal tool set C+- of C++ classes for physics and mathematics has a function for equi-distributing points on spheres which is proven in years of use.) It is impressive how much faster a damped dynamical systems finds its energy minimum than a statistical search, even if this may be augmented by ideas of simulated annealing. It would be against all my intuition if this equilibrium position of points on the sphere would not create the n-polyhedron of minimal volume under the given restriction. Addition: Aha, I omitted Ed's contribution referring to 'Thomson's problem' which I did not yet come across. I'm not sure whether Ed's reservations concerning poles are relevant. The dynamical system I spoke about holds (by use of suitable coordinates) the 'particles' always on the surface. Even if, as the nice Wolfram Demonstration on Thomson's problem says, the equilibrium solution is not unique, I would guess that creating such equilibrium solutions for statistically varied initial conditions would be much more efficient than maximising the volume by statistical search.
Posted 4 years ago
 Most of the Thomson problem solutions have poles going through the center. Try the problem for 12 points. In the method you're suggesting, the vertices of an icosahedron give the solution. Much like the regular hexagon isn't the biggest little hexagon, the icosahedron isn't the biggest 12 point polyhedra, mostly because 12 points at opposite poles is inefficient.Many of my solutions here were started by using a variation of the Thomson code so that points repelled both each other and their pole. I used those solutions as starting points, and then watched them get relentlessly improved over hundreds of improvement runs. It's a great idea, and it's good for starting things off. But the true solutions seem to get a bit whackier.
Posted 4 years ago
 Most of the Thomson problem solutions have poles going through the center. Try the problem for 12 points. In the method you're suggesting, the vertices of an icosahedron give the solution. Much like the regular hexagon isn't the biggest little hexagon, the icosahedron isn't the biggest 12 point polyhedra, mostly because 12 points at opposite poles is inefficient.Many of my solutions here were started by using a variation of the Thomson code so that points repelled both each other and their pole. I used those solutions as starting points, and then watched them get relentlessly improved over hundreds of improvement runs. It's a great idea, and it's good for starting things off. But the true solutions seem to get a bit whackier.
Posted 4 years ago
 Thanks Ed for freeing me from a silly misconception. I identified diameter of a set and diameter of an enclosing sphere! Should not happen! Is it easy for you to say how the biggest little hexagon differs from the regular hexagon?
Posted 4 years ago
 The attached notebook is a modified version of Visualizing the Thomson Problem. It doesn't always work, accounting for the poles and how all the forces interact needs more refinement. But it often works. Some of the generated points provided good starting values for me. I'd eventually like to run some variation of this code up to 30 points and have best results for Thomson with poles. Attachments:
Posted 4 years ago
 After a few more runs on multiple computers, the new records are as follows.5 = 0.144338 ..... 9 = 0.317886 ... 13 = 0.367329 ... 17 = 0.409894 ... 21 = 0.4283476 = 0.195409 ... 10 = 0.332531 ... 14 = 0.380297 ... 18 = 0.415192 ... 22 = 0.4307907 = 0.228451 ... 11 = 0.343976 ... 15 = 0.389857 ... 19 = 0.419319 ... 23 = 0.4348548 = 0.271005 ... 12 = 0.356364 ... 16 = 0.405848 ... 20 = 0.423440 ... 24 = 0.438765 I've fixed some errors in BLPCommunity.nb . The divisor wasn't being reset with each run, so it could get too large. I used to have a much more complicated method, and simplified it a bit too much. Feel free to run this code yourself if you'd like to help me to improve the results. Attachments:
Posted 4 years ago
 The solutions continue to creep forward. 5 = 0.14433760 ..... 9 = 0.31788630 ... 13 = 0.36741690 ... 17 = 0.40993470 ... 21 = 0.428401406 = 0.19540890 ... 10 = 0.33253080 ... 14 = 0.38035100 ... 18 = 0.41535220 ... 22 = 0.430798807 = 0.22845060 ... 11 = 0.34397580 ... 15 = 0.38997030 ... 19 = 0.41940620 ... 23 = 0.434869708 = 0.27100520 ... 12 = 0.35646460 ... 16 = 0.40585650 ... 20 = 0.42350010 ... 24 = 0.43878690 I've updated the BLPCommunity notebook. Attachments:
Posted 4 years ago
 Many more improvements. If you'd like to help me improve them, run the attached notebook in Mathematica 10.5 = 0.1443376 . . 10 = 0.3325308 . . 15 = 0.3900473 . . 20 = 0.42374356 = 0.1954089 . . 11 = 0.3439765 . . 16 = 0.4059011 . . 21 = 0.42859027 = 0.2284506 . . 12 = 0.3564853 . . 17 = 0.4101116 . . 22 = 0.43086288 = 0.2710052 . . 13 = 0.3674903 . . 18 = 0.4155253 . . 23 = 0.43520759 = 0.3178863 . . 14 = 0.3804244 . . 19 = 0.4195572 . . 24 = 0.4388585 Attachments:
Posted 4 years ago
 Looking at the differences between the p5, p6, and p7 solutions I wondered if splitting points with freedom to rotate would recreate the transitions. The ultimate answer is no. However it is a very good starting point for n+1 given a solution to n. Essentially I manually create the local maximum of inter point distances one. This is a problem for example in my p7 solution. I have additional distances length 1, but the volume maximisation actually discards some for a more symmetric polygon.Interesting to me was how close these transitions are structurally. I'm using one transformation on free points, but I expect just one other transform on free co planar sets would transition my slightly warped p6 and p7s into the correct volume maxes. See attached notebook for code and comparisons.David Attachments:
Posted 4 years ago
 Very interesting idea. I attach my latest version of all this, with many improvements and going up to 35 points. 11 = 0.3459434 . . 16 = 0.4059384 . . 21 = 0.4289440 . . 26 = 0.4480637 . . 31 = 0.4595244 12 = 0.3565848 . . 17 = 0.4102651 . . 22 = 0.4330765 . . 27 = 0.4511522 . . 32 = 0.4618691 13 = 0.3682157 . . 18 = 0.4156513 . . 23 = 0.4353794 . . 28 = 0.4537484 . . 33 = 0.4631872 14 = 0.3804943 . . 19 = 0.4196819 . . 24 = 0.4388882 . . 29 = 0.4556745 . . 34 = 0.4652097 15 = 0.3902329 . . 20 = 0.4246072 . . 25 = 0.4428177 . . 30 = 0.4576360 . . 35 = 0.4664916 Your method uses symmetry in a nice way. It would be interesting to find out if that can be done with some of the other best-known-solutions that I have in my notebook. Attachments:
Posted 4 years ago
 My intuition wasn't far off!Rather than sweeping points out to rest against existing restrictions, I drag the restrictions out as required. The established volume maxima lie in these progressions.I expect the capacity to do this is restricted to low n cases with high symmetry. If I were to drag a more complicated set of tethering points it becomes ambiguous: which permitting point progression leads to a maximal volume? I will continue to investigate.The obvious problem creating progressions between n's is that a maximal change from n-1 to n may not be a global maximum for n. The procedures based on random refinement are inherently invulnerable to this.
Posted 4 years ago
 You seem to be onto something here. Using my latest results, try the following: Table[{{n, n + 1}, Intersection[Round[100000 Sort[MyEuclidean[#[[1]], #[[2]]] & /@ Subsets[biggestlittlepolyhedra[[n]], {2}]]], Round[100000 Sort[MyEuclidean[#[[1]], #[[2]]] & /@ Subsets[biggestlittlepolyhedra[[n + 1]], {2}]]]]}, {n, 10, 34}] {{{10,11},{100000}},{{11,12},{100000}},{{12,13},{100000}},{{13,14},{100000}},{{14,15},{100000}},{{15,16},{100000}}, {{16,17},{100000}},{{17,18},{100000}},{{18,19},{100000}},{{19,20},{80881,100000}},{{20,21},{84172,100000}}, {{21,22},{88789,100000}},{{22,23},{37206,100000}},{{23,24},{66878,100000}},{{24,25},{100000}}, {{25,26},{64029,100000}},{{26,27},{69192,100000}},{{27,28},{35135,39229,59992,68950,69689,87104,88930,100000}}, {{28,29},{29935,86265,88761,100000}},{{29,30},{88650,89151,100000}},{{30,31},{89151,100000}}, {{31,32},{73929,91003,100000}},{{32,33},{87444,100000}},{{33,34},{51155,56063,90062,90206,100000}}, {{34,35},{38743,100000}}} In these best known results, found by a random process, there is an improbable amount of overlap in the point distances between solutions for 27 and 28 points. All of these will have overlaps on the longest distance. But there seems to be some repeated structures within this data, something I hadn't noticed. See if you can map together the 27 and 28 point solutions.Another exercise would be to take a solution for $n$, remove two points, and try to get a solution for $n-1$ by combining those points.