Packing twelve spherical caps to maximize tangencies - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T08:51:33Z http://mathoverflow.net/feeds/question/25042 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/25042/packing-twelve-spherical-caps-to-maximize-tangencies Packing twelve spherical caps to maximize tangencies Sam Nead 2010-05-17T17:59:15Z 2010-05-18T15:37:38Z <blockquote> <p>Suppose that $v_i$, for $i \in \{1, 2, \ldots 11, 12\}$, are twelve unit length vectors based at the origin in $R^3$. Suppose that $|v_i - v_j| \geq 1$ for all $i \neq j$. What arrangement of the $v_i$ maximizes the number of pairs $\{i,j\}$ so that $|v_i - v_j| = 1$?</p> </blockquote> <p>If C is a cube of sidelength $\sqrt{2}$ centered at the origin then we can place the $v_i$ at the midpoints of the twelve edges. Taking the convex hull of the $v_i$ gives a cube-octahedron of edge-length one. See <a href="http://en.wikipedia.org/wiki/Cuboctahedron%20" rel="nofollow">here</a> for a picture. If you cut the cubeoctahedron along a hexagonal equator and rotate the top half by sixty degrees you get another polyhedron. Both of these have 24 edges. Are these the unique maximal solutions to the above problem?</p> <p>Notice that if you place the $v_i$ at the arguably nicer vertices of a icosahedron then the $v_i$ become too widely separated. It is easy to check this by making a physical model!</p> <p>I spent some time thinking about areas of spherical polygons and restrictions on the graph of edges (and its dual graph) coming from the Euler characteristic. However, I don't think I got very far - in particular ruling out pentagons seems to be a crucial point that I couldn't deal with. Finally, to explain the problem title: instead of thinking of unit vectors with spacing restrictions, consider the (equivalent) problem of placing twelve identical spherical caps, of radius $\pi/12$, on the unit sphere with disjoint interiors in such a way as to maximize the number of points of tangency. </p> <p>This question was asked of me by an applied mathematician. It comes from a problem involving packing balls in three-space, minimizing some quantity that is computed by knowing pairwise distances. The solution to the <a href="http://en.wikipedia.org/wiki/Kissing_number_problem" rel="nofollow">kissing problem</a> thus justifies the "twelve" appearing in the problem statement. The projection of surrounding balls to a central one gives the spherical caps. </p> http://mathoverflow.net/questions/25042/packing-twelve-spherical-caps-to-maximize-tangencies/25124#25124 Answer by Alexey Tarasov for Packing twelve spherical caps to maximize tangencies Alexey Tarasov 2010-05-18T13:48:32Z 2010-05-18T15:37:38Z <p>Interesting question. I can find answer using my program, which was made for solving Tammes problem for 13 points. But I need some time for answer.</p> <p>UPD: I wrote program. Result: 24 is a maximal number of edges. I did in three steps. First, I enumerated planar graphs with 12 vertices with at least 25 edges, at most 5 edges in a vertex and at most hexagonal faces. Total number of suc graphs is 67497.</p> <p>Second, I eliminated by linear programming by considering values of face angles as variables. My constrains was: 1. angle in triangle is ~1.2310 2. each angle no less than 1.2310 3. sum of angles around vertex is 2*pi 4. opposite angles of rectangle are equal 5. sum of non-opposite angles in rectangle between 3.607 and 3.8213</p> <p>I solve feasibility of this LP problem (with some tolerance) After this step all graph were eliminated.</p>