8
$\begingroup$

Let $C_d$ be a unit edge-length cube in $d$ dimensions. I would like to orient it ("tilt" it) so that the vertical (last) coordinates of its $2^d$ vertices are maximally separated, in the sense that the minimum vertical distance between any two vertices is maximized over all orientations.

For $C_2$ (in standard orientation, edges parallel to Cartesian axes), tilting $\arctan \frac{1}{2} \approx 26.6^\circ$ separates the vertices by $\delta=1/\sqrt{5} \approx 0.447$:

         

For $C_3$ (in standard orientation), I believe that rotating the vector $(0,0,1)$ to lie on the vector $(\frac{1}{4},\frac{1}{2},1)$ results in a vertex separation of $\delta=1/\sqrt{21} \approx 0.218$:

         
My question is:

Q. What is the generalization to $C_d$ for $d>3$? What is the largest vertex separation $\delta$ achievable? Can one always achieve a uniform vertex separation (the same $\delta$ between each vertically adjacent pair), as in $C_2$ and $C_3$?

|cite|improve this question
$\endgroup$
5
$\begingroup$

Given a unit vector $u \in \mathbb R^d$, the "heights" of vertices of the $n$-cube where $u$ is regarded as the vertical direction are the sums of subsets of the entries of $u$. Thus the minimum separation is the minimum difference between the sums of two distinct subsets of these entries. If you take $$u = [1,2,\ldots,2^{d-1}]/\sqrt{1^2 + 2^2 + \ldots (2^{d-1})^2} = \sqrt{\dfrac{3}{4^d-1}}[1,2,\ldots,2^{d-1}]$$ you get uniform separation of $\sqrt{3/(4^d-1)}$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Beautiful! $\mbox{}$ $\endgroup$ – Joseph O'Rourke Jan 5 '15 at 2:01
  • 4
    $\begingroup$ Is it clear that uniform separation gives the optimal separation? (if you change the vector $u$, you might in principle destroy the uniformity, but obtain separation over a (reasonably substantially) larger range: if $u=[1,1,1,\ldots,1]$ then the image of the diagonal is of length $\sqrt d$, whereas here it is $O(1)$). This gives an upper bound for the minimal separation of $\sqrt d/2^d$, whereas here you have a lower bound of approximately $\sqrt 3/2^d$. $\endgroup$ – Anthony Quas Jan 5 '15 at 5:02
  • 1
    $\begingroup$ @AnthonyQuas: Good point! I can verify that for $d=2,3$, the max separation is achieved with uniform separation. $\endgroup$ – Joseph O'Rourke Jan 5 '15 at 11:30
  • $\begingroup$ (Initially I accepted this lucid answer, but as Anthony points out, it doesn't necessarily solve the original question [not that Robert ever claimed it did].) $\endgroup$ – Joseph O'Rourke Jan 6 '15 at 12:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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