Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For a fixed $n$, what is the shape with the smallest volume, such that by rotation and translation, it can cover any $n$-box with dimension $b_1\times \ldots \times b_n$, where $b_1+\ldots+b_n=1$.

I had this problem when I learned some Chinese airlines have restriction on the sum of the dimensions for carry-on baggage, but no restriction on any individual dimension. It is natural to ask how small they can make the compartment, so the baggage still fits.

Let $B(b_1,\ldots,b_n) = \{(x_1,\ldots,x_n)| 0\leq x_i\leq b_i \}$, then clearly the following shape can cover the $n$-boxes.

$$ \bigcup_{b_1\leq \ldots \leq b_n, b_1+\ldots +b_n = 1}B(b_1,\ldots,b_n)$$

The hard part is to prove it has smallest volume. Are there any shape can do this using up even smaller volume? What if I only require the shape to be convex?

share|improve this question
2  
In two dimensions, your shape looks like this (red is $b_2 \in \big[\!\frac12,\frac34\!\big]$, blue is $b_2 \in \big[\!\frac34,1\big]$), while this arrangement has smaller area, so the former is not optimal. –  Rahul Jul 22 '12 at 10:59
    

1 Answer 1

There may be some ideas in the paper by Tirasan Khandhawit, Dimitrios Pagonakis, and Sira Sriswasdi, Lower bound for convex hull area and universal cover problems. The abstract includes this: "...we show that a convex universal cover for a unit closed curve has area at least 0.0879873." Now, anything that covers every unit closed curve in particular covers any rectangle of perimeter 1, so (if you scale it up to perimeter 2) you get some bound on the two-dimensional case of your problem. I don't know whether there's anything in the paper you can use for the 3-dimensional problem, but maybe you can get a feeling for how hard it's likely to be.

EDIT: here's another paper on the two-dimensional problem: Furedi and Wetzel, Covers for closed curves of length two, Period. Math. Hungar. 63 (2011), no. 1, 1–17, MR2853167. They show that the smallest area of a convex set that covers all closed curves of length 2 lies between .386778 and .448504. Of course, this is worse than the .375 your construction gives for covering all rectangles of perimeter 2, but, again, maybe some ideas in the paper apply.

share|improve this answer

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.