Date: Thu, 2 Oct 1997 10:01:47 -0500 (CDT)
From: Dave Rusin <rusin>
To: j.devries@ridder.nl
Subject: Re: Cut Waste Algorithm
Newsgroups: sci.math

In article <01bcc826$04964280$04c8c8c8@sjoerd-de-vries> you write:
>You give some motherplates of different sizes and amounts and a list of
>elements what must cut out this set of motherplates. In such a way that
>there
>is a minimum of waste from the motherplates.
>
>Does somebody have a algorithm for this kind of problem?

This is unsolved even in the very specialized case in which: there is
one "motherplate", it is a large square or disk, and the "elements" are
identical squares or disks. This special case is known as the
"sphere-packing problem". 

However, I suspect you are not interested in the absolute minimum
waste so much as in keeping the waste small. In that case, one can
certainly try pertubation techniques: begin with a reasonable placement
of the elements, then try incremental changes in location and orientation
so as to reduce waste.

A colleague once shared this anecdote: he was required to fill as much
gunshot as possible into a large sphere (to make it as heavy as possible).
He ran some complicated analysis of the situation but in the end could
not do as well as the soldiers' previous technique: throw as much shot
as possible into the sphere, put the sphere in a truck, drive on a bumpy
road, and keep refilling the sphere as the gunshot settled!

Nowadays, presumably, a computer animation could take the place of that
bumpy drive; that's essentially what pertubation methods do.

Your problem also suggests another classic problem: if for example all
the "elements" and "motherplates" are  1 x n  rectangles for different
integers  n, there is a finite set of configurations to test in order
to choose the one with minimal waste. But this is called the "knapsack
problem", and does not admit an efficient solution if the absolute
optimum must be found.

dave