[comp.theory] Complexity of a Packing Problem

wolffram@andor1.rz.uni-karlsruhe.de (Jochen WOLFFRAM) (04/29/91)

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.

Any help is greatly appreciated.

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

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)