**Next message:**Elaine Persall: "Re: RP and packing problem"**Previous message:**Georges Fadel: "Re: RP and packing problem"**Maybe in reply to:**Ilkka Tapio Ikonen: "RP and packing problem"**Next in thread:**Elaine Persall: "Re: RP and packing problem"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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." (-)

**Next message:**Elaine Persall: "Re: RP and packing problem"**Previous message:**Georges Fadel: "Re: RP and packing problem"**Maybe in reply to:**Ilkka Tapio Ikonen: "RP and packing problem"**Next in thread:**Elaine Persall: "Re: RP and packing problem"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*
This archive was generated by hypermail 2.1.2
: Tue Jun 05 2001 - 22:39:13 EEST
*