Minimum size hypercube touching a vertex of a rotated hypercube
up vote
2
down vote
favorite
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.
linear-algebra geometry fourier-transform
asked Jan 2 '16 at 19:14
D0SBoots
16317
add a comment |
up vote
2
down vote
favorite
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.
linear-algebra geometry fourier-transform
asked Jan 2 '16 at 19:14
D0SBoots
16317
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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.
linear-algebra geometry fourier-transform
asked Jan 2 '16 at 19:14
D0SBoots
16317
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.
linear-algebra geometry fourier-transform
linear-algebra geometry fourier-transform
asked Jan 2 '16 at 19:14
D0SBoots
16317
asked Jan 2 '16 at 19:14
D0SBoots
16317
edited Nov 21 at 9:24
asked Jan 2 '16 at 19:14
D0SBoots
16317
asked Jan 2 '16 at 19:14
D0SBoots
16317
asked Jan 2 '16 at 19:14
D0SBoots
16317
16317
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1597475%2fminimum-size-hypercube-touching-a-vertex-of-a-rotated-hypercube%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
