From: Michael Campbell <michael.campbell@...>
Date: 2005-06-30T06:41:26+09:00
Subject: Re: Programmers Contest: Fit pictures on a page

On 6/29/05, Phrogz <gavin@refinery.com> wrote:

> Karl, I think you are (incorrectly) assuming that all the pictures have
> the same size or aspect ratio. It's a bin-packing problem. Given a
> fixed-size space and differing-sized objects, the ways in which they
> are placed very much affect the amount of leftover space.

How so?  Given that any suitable, rule-conforming arrangement of
objects has them all inside the bin, no overlapping, etc., the volume
of the bin - the sum of the volume of the objects = leftover volume;
how they are placed nor how they are shaped has any bearing on the
problem.   It SOUNDS like the OP is trying to maximize the
"contiguousness" of the leftover space, but that's not how it reads. 
Not even sure how you'd measure that; minimize the magnitude of the of
the length of the perimiter?

Is the problem then to see HOW one might place 'n' rectangular shapes
inside a rectangular boundry such that none of the placed shapes
overlap each other, nor exceed the perimeter of the boundry?

Or is it possibly, what's the minimum number of (uniformly
dimensioned?) boundries required to FIT the n shapes?  THIS sort of
problem is one I come across regularly in woodworking; how do I
minimize the number of sheets of plywood (etc.) needed to cut out all
the pieces of a given construction?