2
$\begingroup$

I have the following question:

Let be (C_n) a sequence of m-dimensional hypercubes such that the series over the volumes of this cubes converges. I assume that it's possible to place those cubes in the m-dimensional space in such a way that those are pairwise disjoint and contained in a bounded set. However, I do not see how to prove that. Does somebody know a referecne or a proof?

$\endgroup$
4
  • 1
    $\begingroup$ Can you solve the 2-dimensional case where there is a square of side $1/n$ for each $n$? The total area is $\pi^2/6$. $\endgroup$ Commented Oct 30, 2022 at 0:05
  • $\begingroup$ The case $m=2$ is discussed in Stefan Hougardy, On packing squares into a rectangle, Computational Geometry, Volume 44, Issue 8, October 2011, Pages 456-463, sciencedirect.com/science/article/pii/S0925772111000319 $\endgroup$ Commented Oct 30, 2022 at 0:34
  • 2
    $\begingroup$ Abstract We prove that every set of squares with total area $1$ can be packed into a rectangle of area at most $2867/2048=1.399\dots$ . This improves on the previous best bound of $1.53$. Also, our proof yields a linear time algorithm for finding such a packing. $\endgroup$ Commented Oct 30, 2022 at 0:36
  • $\begingroup$ Thank you very much, the paper is amazing. $\endgroup$ Commented Oct 30, 2022 at 11:28

1 Answer 1

2
$\begingroup$

This can be generalized:

Let $(C_n)$ be a sequence of sets of $\mathbb{R}^m$ such that $\sum_n \text{diam}(C_n)^m=S<\infty$. Then we can find disjoint sets $(D_n)_n$ such that $D_n$ is a translate of $C_n$ and $\bigcup_{n=1}^\infty D_n$ is bounded.

To prove that, reorder the sets $C_n$ so that the sequence $d_n:=\text{diam}(C_n)$ is decreasing. Now consider a ball $B\subseteq\mathbb{R}^m$ of volume $4^m S$. Then we can find by recursion a sequence of points $p_n\in B$ such that for any $i<j$ we have $d(p_i,p_j)>2d_i$. To do this we just need to choose $p_n\in B$ outside the closed balls $B(p_1,2d_1),B(p_2,2d_2),\dots,B(p_n,2d_n)$: this is possible because, if $m$ is Lebesgue measure, $m(B)=4^mS=\sum_{i=1}^\infty(2\text{diam}(C_i))^m\geq\sum_{i=1}^{n-1}(4\text{diam}(C_i)^m)>\sum_{i=1}^{n-1}m(B(p_i,2d_i))$.

Then choose $D_n$ to be some translate of $C_n$ containing $p_n$. Clearly $\bigcup_n D_n$ is bounded, and the $D_i$ are disjoint because for any $i<j$, $d(p_i,p_j)>2\text{diam}(C_i)\geq \text{diam}(C_i)+\text{diam}(C_j)$.

$\endgroup$
1
  • $\begingroup$ Thank you very much, now I understand. $\endgroup$ Commented Oct 30, 2022 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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