Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!stanford.edu!msi.umn.edu!math.fu-berlin.de!ira.uka.de!news
From: wolffram@andor1.rz.uni-karlsruhe.de (Jochen WOLFFRAM)
Newsgroups: comp.theory
Subject: Complexity of a Packing Problem
Message-ID: <1991Apr29.130212.5733@ira.uka.de>
Date: 29 Apr 91 13:02:12 GMT
Sender: news@ira.uka.de (USENET News System)
Organization: University of Karlsruhe, Germany
Lines: 18


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)