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?

Improve this question
$\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$
    – Brendan McKay
    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$
    – Gerry Myerson
    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$
    – Gerry Myerson
    Commented Oct 30, 2022 at 0:36
  • $\begingroup$ Thank you very much, the paper is amazing. $\endgroup$
    – Maxim Glyzhev
    Commented Oct 30, 2022 at 11:28

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much, now I understand. $\endgroup$
    – Maxim Glyzhev
    Commented Oct 30, 2022 at 14:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .