Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Motivation

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.

Tiling in 3d

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.

Question

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$?

share|improve this question
7  
What a beautiful image! :-) –  Joseph O'Rourke Dec 3 '11 at 16:47
1  
Mapping $V_P$ to their normal vectors on the unit sphere, you are seeking the optimal packing of disks on that sphere. So starting with such a packing, it seems the question is whether you can go backwards from $V_P$ to $V$. Is this a correct interpretation? –  Joseph O'Rourke Dec 3 '11 at 16:56
    
That would be a great way to deal with the problem, especially given the literature on circle packings on the sphere. I could not find an obvious way to do it. You always seem to need vectors that allow new planes to pop in. (Thanks, I am quite proud of it, here's a hyperboloid from the same renderer: maxwelldemon.com/2011/11/06/hyperboloid-lighting) –  Edmund Harriss Dec 3 '11 at 17:05
    
Please permit a dumb question for sake of my clarity? Do all the planes pass through or contain the point (0,0,0) (or otherwise have a point in common)? Gerhard "Ask Me About System Design" Paseman, 2011.12.03 –  Gerhard Paseman Dec 3 '11 at 18:39
    
Yes, all the vectors are assumed to start from (0,0,0), so all the planes will pass through this point. –  Edmund Harriss Dec 3 '11 at 19:01
show 2 more comments

2 Answers

up vote 5 down vote accepted

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:
           Cuboctahedron
The angles between these lines/planes is either $90^\circ$ or about $63.6^\circ$ (or $116.4^\circ$) $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$.

So: Is there an arrangement of four vectors $V$ that yields this optimal line packing? Answer: No, $60^\circ$ is the optimal for $n=4$. See Henry Cohn's argument in the comments.


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$.
           Icosahedron
The tips of the normal lines form the vertices of an icosidodecahedron.

share|improve this answer
1  
Where does the $63.6^\circ$ come from? Maybe I'm making a silly mistake, but it sounds impossible (since it is larger than the $63.4^\circ$ for the icosahedron). I think the answer should be $60^\circ$ for the tetrahedron. Specifically, there are two types of planes, depending on whether the corresponding pairs of vertices are disjoint. If they are, you get $90^\circ$. If they aren't, you get the angle between the projections of the other vertices orthogonal to the common vertex, which is $120^\circ$ (or $60^\circ$). –  Henry Cohn Dec 4 '11 at 2:35
1  
If I've done this right, then $60^\circ$ is optimal for four vectors: given any one of them, the projections of the others orthogonal to it form three points on a circle, at can be separated by at most $120^\circ$, and then the $\pm 1$ issue gives $60^\circ$. –  Henry Cohn Dec 4 '11 at 2:36
1  
@Henry: I neglected to normalize vectors before taking the ArcCos() :-/. Thanks for catching the error! –  Joseph O'Rourke Dec 4 '11 at 2:50
2  
Great, thanks. So the answer to your question is no, then ($60^\circ$ is optimal for four vectors). –  Henry Cohn Dec 4 '11 at 3:03
2  
Nice, Henry! Now on to $n=5,6,\ldots$. :-) –  Joseph O'Rourke Dec 4 '11 at 14:41
show 4 more comments

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.

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.

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.

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.$$

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.$$

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}$.

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 (?).

share|improve this answer
    
This looks like an interesting method, especially as it seems to have plenty of choice, giving a wide range of "reasonable" solutions. Thanks! –  Edmund Harriss Dec 5 '11 at 4:31
    
When I was in school, I wanted to show that any subset of $\mathbb Z_{3^n}$ which has at least $2^n+1$ element has to contain an arithmetic progression of length 3. I did not prove it, and later I found a counterexample which used the idea described above. (Unfortunately I do not remember the authors.) –  Anton Petrunin Dec 6 '11 at 1:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.