Placing points on a sphere so that no 3 lie close to the same plane - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T13:17:14Z http://mathoverflow.net/feeds/question/82565 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/82565/placing-points-on-a-sphere-so-that-no-3-lie-close-to-the-same-plane Placing points on a sphere so that no 3 lie close to the same plane Edmund Harriss 2011-12-03T16:27:05Z 2011-12-28T01:13:21Z <p><strong>Motivation</strong></p> <p>I am working with arbitrary parallelopiped tilings given by projection from a higher dimensional space. The collection of tiles, and some properties of the higher dimensional space are specified by a finite collection of vectors forming the edges of the tiles. The tiles themselves are parallelopipeds given by all choices of three vectors from this set. A patch of such a tiling is shown below.</p> <p><img src="http://www.mathematicians.org.uk/eoh/gallery/Sort_of_balls_render_sm.png" alt="Tiling in 3d"></p> <p>The tricky thing is trying to find sets of vectors where none of the parallelopipeds are nearly flat. This lead me to a more general question, a sort of dual problem to packing circles on a sphere. </p> <p><strong>Question</strong></p> <p>Given $V$ a set of 3d vectors in general position, so that no two lie on the same line and no three lie on the same plane. Without loss of generality, we may assume they are unit vectors. We can consider $V_P$, the set of planes generated by all pairs of vectors in $V$. What arrangements of vectors $V$ will maximise the smallest angle between two planes in $V_P$?</p> http://mathoverflow.net/questions/82565/placing-points-on-a-sphere-so-that-no-3-lie-close-to-the-same-plane/82576#82576 Answer by Anton Petrunin for Placing points on a sphere so that no 3 lie close to the same plane Anton Petrunin 2011-12-03T19:45:40Z 2011-12-05T04:19:00Z <p>I do not think you expect to find an optimal configuration. I will describe a general idea to produce a reasonable one. Hope someone will give you a better answer. </p> <p>In the answer I looking for a configuration of points on the plane such that angles between lines through pairs of these points are big enough. This construction can be modified easily for your needs.</p> <p>Fix some natural number $N$. Choose a half-circle $\gamma$. Let $M$ be the number of integer points on $\gamma$ with all coordinates in $[0,N]$. One can choose $\gamma$ so that $M$ is quite big; say $M\gg C\cdot N^{2/5}$ is easy to arrange, but one can do better.</p> <p>Note that for any two distinct pairs $(x,y)$ and $(v,w)$ of integer points on $\gamma$ we have $$|(y-x)+(w-v)|\ge 1.$$</p> <p>For each integer point $x=(x_1,x_2)\in\gamma$, consider the number $$\bar x=x_1+(2\cdot N)\cdot x_2$$ All $\bar x$'s form a set $\bar X$ of integers in $[0,(2\cdot N)^2]$ such that for any two distinct pairs $(\bar x,\bar y)$ and $(\bar v,\bar w)$ of numbers in $\bar X$, we have $$|(\bar y - \bar x)+(\bar w - \bar v)| \ge 1.$$</p> <p>Mark all points on a circle with central angles $\tfrac{\bar x\cdot\pi}{(2\cdot N)^2}$, $\bar x\in \bar X$. Note that the angles between the lines through these points will be $\ge \tfrac{\pi}{2\cdot (2\cdot N)^2}$.</p> <p>If you look for a set of $n$ points, you it sufficient to take $N\gg n^{5/2}$ and therefore the angle will be $\gg 1/n^5$. This estimate can be improved, but I do not think you can get $\gg 1/n^2$ on this way; this might be the optimal asymptotic (?).</p> http://mathoverflow.net/questions/82565/placing-points-on-a-sphere-so-that-no-3-lie-close-to-the-same-plane/82593#82593 Answer by Joseph O'Rourke for Placing points on a sphere so that no 3 lie close to the same plane Joseph O'Rourke 2011-12-04T02:14:24Z 2011-12-28T01:13:21Z <p>This is not an answer, just a remark. I find your question interesting even for small values of $n=|V|$. For example, if $n=4$, then choosing $V$ as the vertices of a regular tetrahedron, the $\binom{4}{2}=6$ planes $V_P$ determine six normal lines that define a cuboctahedron: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://people.csail.mit.edu/~orourke/MathOverflow/Cuboctahedron.jpg" alt="Cuboctahedron"> <br /> The angles between these lines/planes is either $90^\circ$ or <strike>about $63.6^\circ$ (or $116.4^\circ$)</strike> $60^\circ$ (or $120^\circ$). Now, the optimal packing of six lines is known (Conway, Hardin, Sloane) to be the six diameters of the icosahedron. The minimum angle determined by those diameters is a bit larger, if I've calculated correctly: $63.4^\circ$.</p> <p>So: Is there an arrangement of four vectors $V$ that yields this optimal line packing? <b>Answer:</b> No, $60^\circ$ is the optimal for $n=4$. See Henry Cohn's argument in the comments. <hr /> Here is Edmund's suggestion for $n=6$: $V$ is given by half the vertices of an icosahedron (blue), which generate 15 normal lines (red) passing through the midpoints of the icosahedron's 30 edges, with the normal lines separated by $49.7^\circ$. <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://people.csail.mit.edu/~orourke/MathOverflow/Icosahedron6.jpg" alt="Icosahedron"> <br /> The tips of the normal lines form the vertices of an <a href="http://en.wikipedia.org/wiki/Icosidodecahedron" rel="nofollow">icosidodecahedron</a>.</p>