Accession Number:

ADA011835

Title:

On Packing Squares with Equal Squares

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1975-03-01

Pagination or Media Count:

12.0

Abstract:

The following problem arises in connection with certain multidimensional 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 alpha squared unit squares can be successfully packed. However, if alpha is not an integer, the problem becomes much more complicated. Intuitively, one feels that for alpha N 1100, say, where N is an integer, one should pack N squared unit squares in the obvious way and surrender the uncovered border area which is about alpha50 as unusable waste. After all, how could it help to place the unit squares at all sorts of various skew angles. In this note, the authors show how it helps. In particular, the authors prove that one can always keep the amount of uncovered area down to at most proportional to alpha sup711, which for large alpha is much less than the linear waste produced by the natural packing above.

Subject Categories:

  • Theoretical Mathematics
  • Containers and Packaging

Distribution Statement:

APPROVED FOR PUBLIC RELEASE