On Tue, 14 Jan 1997 09:09:34, Marshall Burns wrote:
> > Program will read part STL files and find a good packing for them.
> > Meaning, it tries to pack them as tightly as possible without part
> > or build envelope intersections. This program is meant to be a tool for
> > human operator
>
> Dear Ilkka,
> That's a great idea. Let me ask, do you expect to be able to prove
> mathematically that you have obtained the tightest possible packing
> for a given collection? What limitations on shape would allow you to
> provide such a mathematical proof?
Marshall,
It will be *very* surprising if Ilkka gives a *polynomial*-time algorithm
for solving the 3D packing problem and proves it always finds an optimal
solution. The 1D analog of the problem (the "bin-packing" problem) already
belongs to the so-called NP-Complete class of problems: find a
polynomial-time algorithm (that is, an algorithm whose running time is
proportional to a polynomial in the size of the input), and you found such
an algorithm for thousands of problems for which only exponential-time
algorithms are known but no polynomial-time algorithms. Assumptions like
"all the objects are boxes, and even axis-parallel boxes (no rotations
allowed)" don't make the problem easier. The question whether there exists
any polynomial-time algorithm for this class of problems is a long standing
problem in computational complexity since the late 70's. There is a deep
theory on *approximation* algorithms for these problems, where you get
solutions which are, say, (1+epsilon) times the size of the optimal
solution (assuming minimum is sought).
Gill.
------------------------------------------------------------------------
Gill Barequet, Ph.D. Phone: (410) 516-5298
Center for Geometric Computing Fax: (410) 516-6134
Dept. of Computer Science E-mail: barequet@cs.jhu.edu
3400 N. Charles St. WWW: http://www.cs.jhu.edu/~barequet
Johns Hopkins University (Priv. Phone & Fax: (410) 602-9703)
Baltimore, MD 21218-2694
U.S.A. "Life is NP-Hard." (-)
This archive was generated by hypermail 2.1.2 : Tue Jun 05 2001 - 22:39:13 EEST