[sci.math] Complexity of a Packing Problem

wolffram@andor1.rz.uni-karlsruhe.de (Jochen WOLFFRAM) (05/17/91)

Some weeks ago I posted the following question:

>Consider the following problem:
>  Given a region R and *one* figure P consisting of
>  not necessarily connected unit squares, e.g. both cut from an infinite
>  checkerboard.
>  What is the maximal number of copies of P which can be placed into R
>  so that they do not overlap each other?
>
>Question:
>  Is the corresponding decision problem NP-complete?
>Note:
>  The more general problem with a finite set of figures is known to
>  be NP-complete.

The answer is YES. The proof can be found in
  Fowler, Paterson, Tanimoto:
  Optimal packing and covering in the plane are NP-complete.
  Information Processing Letters 12(3), 133-137, 1981

Many thanks for all hints I got.

Jochen Wolffram
(wolffram@andor.rz.uni-karlsruhe.de)