Friday, December 29, 2017

Maximally Separated Points on a Sphere

One of the designs for a seven-sided die is a sphere truncated at 7 points as far apart from each other as possible. The die doesn't have opposite and parallel sides so there isn't a face for writing the result on. Still the technique is general and could be used to create dice with anywhere between 5 and 100 sides.

How do we find points as far apart as possible from each other? For most values of n the problem is hard. One approach is to sum the pairwise distances of the points and use gradient ascent to find a maximum. The objective function is not convex and has local maxima, but if you think a local maximum is better than nothing, here is code find one. The code uses Euclidean distance, though I wonder if using the angle between two points would work better.  The partial derivatives are with respect to the θ and φ of spherical coordinates since we are constrained to the surface of the sphere.

Running the code:

  $ ./maximally_separated_points_on_sphere.py -n 7
  (0.139, -0.576, -0.805)
  (-0.191, 0.963, 0.191)
  (-0.608, 0.338, -0.718)
  (0.173, 0.142, 0.975)
  (0.884, 0.38, -0.273)
  (-0.855, -0.418, 0.308)
  (0.458, -0.828, 0.322)
  31.530926 

The output contains the coordinates of the 7 points found and the value of the objective function at those points.  A convex polytope can be defined in polymake using a set of points—in which case it finds the convex hull—or a set of half spaces—in which case it finds the intersection. Polymake requires homogeneous coordinates.

  $ polymake
  polytope > $p = new Polytope(POINTS => 
    [[1, 0.139, -0.576, -0.805],
     [1, -0.191, 0.963, 0.191],
     [1, -0.608, 0.338, -0.718],
     [1, 0.173, 0.142, 0.975],
     [1, 0.884, 0.38, -0.273],
     [1, -0.855, -0.418, 0.308],
     [1, 0.458, -0.828, 0.322]]);

  polytope > print $p->VERTICES_IN_FACETS;
  {1 2 5}
  {0 2 5}
  {0 2 4}
  {1 3 5}
  {1 3 4}
  {1 2 4}
  {3 4 6}
  {3 5 6}
  {0 5 6}
  {0 4 6}

Polymake tells us the polyhedron has ten faces. This website says there are 5 topologically different polyhedra with 7 vertices and 10 faces. Since polymake tells us which vertices belong to which faces, we can use Blender to visualize the polyhedron.



Following the instructions above yields this picture:
Our polyhedron is topologically equivalent to a pentagonal bipyramid. The figure is the dual of the 7-sided polyhedron we would like to make a die out of. The dual can be found in polymake using polarize:

  polytope > $dual = polarize($p);

  polytope > print convert_to<Float>(
    dehomogenize($dual->VERTICES));
  1.455537382 -0.7147719412 -0.1762669144
  1.083809015 0.804520317 0.8537214292
  -0.4415750134 -0.506366941 1.52830861
  1.059871785 -0.6049596605 -1.125593382
  -0.8893855532 -1.073711966 -0.7114555899
  -0.2646212759 -1.291044842 1.009076016
  -1.423698754 0.1131924589 -0.7895112253
  0.2939932965 0.9002156047 -1.208914314
  0.4841557507 1.557693116 0.211262627
  -1.274046573 0.7045065006 0.518151282

  polytope > print $dual->VERTICES_IN_FACETS;
  {1 2 8 9}
  {0 3 4 5}
  {0 1 2 5}
  {3 4 6 7}
  {2 4 5 6 9}
  {0 1 3 7 8}
  {6 7 8 9}

Polymake lists the vertices in a face in ascending order. Blender requires that we list the vertices in the order they occur as we travel around the polygon—otherwise the wireframe will have extra edges in the faces. Trial and error was used to find the correct order:
The polyhedron is topologically equivalent to a pentagonal prism.

Tuesday, December 26, 2017

Polyhedral Duality

Blender is 3D modeling software. It has an operation called bevel which can be used to convert a cube into an octahedron. When you are in Edit Mode, type w to bring up the Specials menu.


The operation converts each face of the cube into a vertex and each vertex of the cube into a face. Edges become edges, although the orientation of each edge rotates by 90º.

The f-vector of a polyhedron is a triple containing the number of vertices, edges, and faces. The f-vector of the cube is (8, 12, 6) and the f-vector of the octahedron is (6, 12, 8). If a polyhedron can be converted to another polyhedron by the bevel operation, the f-vector of the first must be the same as the f-vector of the second reversed.

An icosahedron has f-vector (12, 30, 20) . The bevel operation converts it to a dodecahedron with f-vector (20, 30, 12).


The face lattice of a polyhedron shows which edges belong to which faces, and which vertices belong to which edges. Since the cube and the octahedrons are dual polyhedra, the face lattice of an octahedron
is an upside down version of the face lattice of a cube.
For the labels to agree we must map the faces, edges, and vertices of the first lattice to the vertices, edges, and faces second respectively.  The mapping should match the way the bevel operation maps them.

The bevel operation converts a tetrahedron into tetrahedron. The f-vector of the tetrahedron is a palindrome: (4, 6, 4). The tetrahedron is said to be self-dual.

One last note about duality. Dual polyhedra have isomorphic symmetry groups and isomorphic alternating groups.

Sunday, December 10, 2017

How to Draw Platonic Solids

I've been held back from posting more about polyhedra by my inability to create the necessary graphics. A picture is worth a thousand words, and if it's a picture of a polyhedron use 3D modeling software to create it. I used Blender to create the above image. I made a screencast of how I did it: