Xref: utzoo sci.math:17483 comp.theory:1998
Newsgroups: sci.math,comp.theory
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!ira.uka.de!news
From: wolffram@andor1.rz.uni-karlsruhe.de (Jochen WOLFFRAM)
Subject: RE: Complexity of a Packing Problem
Message-ID: <1991May17.091443.13190@ira.uka.de>
Sender: news@ira.uka.de (USENET News System)
Organization: University of Karlsruhe, Germany
Date: Fri, 17 May 1991 09:14:43 GMT
Lines: 24

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)