BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-75-483
       ENTRY:: August 23, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On packing squares with equal squares.
        TYPE:: Technical Report
      AUTHOR:: Erdoes, Paul
      AUTHOR:: Graham, Ronald L.
        DATE:: March 1975
       PAGES:: 9
    ABSTRACT:: The following problem arises in connection with certain
               multi-dimensional stock cutting problems:

               How many non-overlapping open unit squares may be packed into
               a large square of side $\alpha$?

               Of course, if $\alpha$ is a positive integer, it is trivial
               to see that unit squares ean be successfully packed. However,
               if $\alpha$ is not an integer, the problem beeomes much more
               complicated. Intuitively, one feels that for $\alpha$ = N +
               1/100, say, (where N is an integer), one should pack $N^2$
               unit squares in the obvious way and surrender the uncovered
               border area (which is about $\alpha$/50) as unusable waste.
               After all, how could it help to place the unit squares at all
               sorts of various skew angles?

               In this note, we show how it helps. In particular, we prove
               that we can always keep the amount of uncovered area down to
               at most proportional to ${\alpha}^{7/11}$, which for large
               $\alpha$ is much less than the linear waste produced by the
               "natural" packing above.
       NOTES:: [Adminitrivia V1/Prg/19950823]
         END:: STAN//CS-TR-75-483