Today I want to give details on some possible applications of algorithm **3**, that I outlined in my last post on tangram puzzles.

The first application is 2D packing, which is a variation on bin packing.

The 2-dimensional packing problem I want to solve is defined as follows:

Given a set of simple polygons **S**, find the smallest rectangle **R** and a packing such that the polygons in **S** are packed inside the rectangle **R**.

Notice that one of the constraints on problem is that we need to find the *smallest* rectangle that can be packed with the polygons in **S**. I don’t know if the algorithm I outline below satisfies this constraint, a later post will revisit this issue. My algorithm also restricts the rectangle **R** to be a square.

The algorithm for solving the above packing problem is as follows:

0. Set a tolerance ε.

1. Set a step size, **dl**, of 1.

2. Create a square, **R**, with sides of length **l** = 1.

3. Check using algorithm **3** (position_puzzle_pieces) if the polygons in **S** can be packed into **R**.

4. If **S** can be packed into **R**, then set **l** = **l**–**dl**.

5. If **S** cannot be packed into **R**, then set **l** = **l**+**dl**.

6. If steps 3 through 5 have looped more than once, then goto step 7. Otherwise, if for the last two loops of steps 3 through 5:

(1) **S** couldn’t be packed into **R**, then set **dl** = 2**dl**;

(2) **S** could be packed into **R**, then set **dl** = 2**dl**;

(3) otherwise **dl** = **dl**/2.

7. If, in step 3, **S** could be packed into **R** and **dl** < ε, then stop; otherwise goto step 3.

The above algorithm uses a binary search in combination with **position_puzzle_pieces** to find the optimal length **l**. The algorithm does assume that if **S** cannot be packed into a square with sides of length **x**, then **S** cannot be packed into any square with sides of length less than **x**.

That’s it for today. There are a couple other applications I want to talk about tomorrow and hopefully I’ll also have time to delve more deeply into variations on the position_puzzle_pieces algorithm.