Consider the length-2 n-cube with vertices $(\pm 1,\pm 1,\cdots ,\pm 1)$, which we will apply some rotation to.

Let $V = \{(a_1, a_2, \cdots, a_n), (b_1, \cdots, b_n), \cdots\}$ be the set of vertices in the rotated hypercube. I am looking for $\min(\max(\{|x_1|, \cdots, |x_n|\}) : x \in V)$. Since $\max(\{|x_1|, \cdots, |x_n|\})$ is equivalent to the size of the (origin-centered, axis-aligned) hypercube which touches vertex $x$, the overall goal is to find the minimum-size hypercube which touches at least one vertex in $V$.

Another way of looking at it is that if you place an axis-aligned bounding box around $V$, the goal is to find the smallest dimension-component of the box.

By symmetry, it's apparent that there will be an even number of vertices with this minimum, and the resulting value is obviously $\ge 1$. But despite it seeming like this should be a value that you can compute directly from the rotation matrix, I haven't found a simple solution yet.

For my particular problem, there is additional structure: $n=64$ and the rotation is that of the 2D 8x8 DCT used by JPEG.

  • $\begingroup$ It has been a while since you ask this question, has there been any progress? $\endgroup$
    – yarchik
    Oct 30, 2022 at 11:45
  • $\begingroup$ No, I never got any further with it. $\endgroup$
    – D0SBoots
    Oct 31, 2022 at 21:29


You must log in to answer this question.

Browse other questions tagged .