Message Boards Message Boards

12
|
31565 Views
|
26 Replies
|
50 Total Likes
View groups...
Share
Share this post:

Biggest Little Polyhedra

Posted 9 years ago

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.

biggest little polyhedra

Most of these solutions could doubtlessly be improved or made more exact. If anyone can provide any improvements, please post them.

Attachments:
POSTED BY: Ed Pegg
26 Replies

I made a Demonstration out of my results so far, Biggest Little Polyhedron.

Latest results:
06=0.1954089 . 11=0.3459434 . 16=0.4059384 . 21=0.4289440 . 26=0.4481036 . 31=0.4595631
07=0.2284506 . 12=0.3565848 . 17=0.4102651 . 22=0.4330765 . 27=0.4512001 . 32=0.4620735
08=0.2710052 . 13=0.3682157 . 18=0.4156513 . 23=0.4353794 . 28=0.4537778 . 33=0.4632111
09=0.3178863 . 14=0.3804943 . 19=0.4196819 . 24=0.4388882 . 29=0.4557287 . 34=0.4652728
10=0.3325308 . 15=0.3902329 . 20=0.4246072 . 25=0.4428177 . 30=0.4576687 . 35=0.4665434

One idea I finally programmed -- two 3-vertices can be connected by a unit rod. I made a program that would slightly move that unit rod around. Running against everything -- no improvements. It would probably help for new point sets, but the current point sets have computer months of constant improvements.

Another idea, not yet programmed. Take a 3 vertex. Remove one unit rod and treat like a 2-vertex, and see if an improvement is found.

POSTED BY: Ed Pegg

In my last post I was struggling to generalise the transition I'd chosen from five points to six. It felt slightly too neat that the progression continued back to a regular tetrahedron. Reversing the change, we see a transition pulling a duplicate edge off into the tetrahedron internally.

I tried to do the same from two opposing edges of a tet', and this sweep does pass through the maximal eight pointer!

code

four sweep eight

POSTED BY: David Gathercole

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.

POSTED BY: Ed Pegg

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.

gif

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 BY: David Gathercole

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 BY: Ed Pegg

Looking at the differences between the p5, p6, and p7 solutions I wondered if splitting points with freedom to rotate would recreate the transitions.

p5 to p6

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.

p6 to p7

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 BY: David Gathercole

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.4237435
6 = 0.1954089 . . 11 = 0.3439765 . . 16 = 0.4059011 . . 21 = 0.4285902
7 = 0.2284506 . . 12 = 0.3564853 . . 17 = 0.4101116 . . 22 = 0.4308628
8 = 0.2710052 . . 13 = 0.3674903 . . 18 = 0.4155253 . . 23 = 0.4352075
9 = 0.3178863 . . 14 = 0.3804244 . . 19 = 0.4195572 . . 24 = 0.4388585

Attachments:
POSTED BY: Ed Pegg

The solutions continue to creep forward.

5 = 0.14433760 ..... 9 = 0.31788630 ... 13 = 0.36741690 ... 17 = 0.40993470 ... 21 = 0.42840140
6 = 0.19540890 ... 10 = 0.33253080 ... 14 = 0.38035100 ... 18 = 0.41535220 ... 22 = 0.43079880
7 = 0.22845060 ... 11 = 0.34397580 ... 15 = 0.38997030 ... 19 = 0.41940620 ... 23 = 0.43486970
8 = 0.27100520 ... 12 = 0.35646460 ... 16 = 0.40585650 ... 20 = 0.42350010 ... 24 = 0.43878690

I've updated the BLPCommunity notebook.

Attachments:
POSTED BY: Ed Pegg

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.428347
6 = 0.195409 ... 10 = 0.332531 ... 14 = 0.380297 ... 18 = 0.415192 ... 22 = 0.430790
7 = 0.228451 ... 11 = 0.343976 ... 15 = 0.389857 ... 19 = 0.419319 ... 23 = 0.434854
8 = 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 BY: Ed Pegg

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 BY: Ed Pegg

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 BY: Ulrich Mutze

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 BY: Ed Pegg

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 BY: Ulrich Mutze

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 BY: Ed Pegg

Trimmed this message away, really old results.

POSTED BY: Ed Pegg

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.419175
5 . 0.144338 ... 10 . 0.332531 ... 15 . 0.389714 ... 20 . 0.423270
6 . 0.195409 ... 11 . 0.343976 ... 16 . 0.405805 ... 21 . 0.428347
7 . 0.228451 ... 12 . 0.356288 ... 17 . 0.409869 ... 22 . 0.430727
8 . 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 BY: Ed Pegg

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

nine points

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 BY: Ed Pegg
Posted 9 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 BY: Robin Houston

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 BY: Ed Pegg

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. eight points

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 BY: Ed Pegg

Awesome. Not sure if I will be able to sleep tonight.

POSTED BY: Todd Rowland

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:

seven points

POSTED BY: Ed Pegg

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. optimal 6 point solution

POSTED BY: Ed Pegg

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

Five points

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 BY: Ed Pegg

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 BY: Todd Rowland

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 BY: Todd Rowland
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract