Is there an efficient algorithm for solving tiling puzzles?

Question

As an example of the type of problem, consider Stewart Coffin's Cruiser puzzle:

Let R be a 48 × 31 rectangle. Let T be a 30°-60°-90° triangle with hypotenuse 34.565 (so legs are 17.2825 and 29.934). Let P be a right trapezoid with base 20.0982 and altitudes 27.1178 and 15.514. Show how to place two copies of T and two copies of P inside R with no overlap.

Solution

The algorithm should be able to solve for any number of polygons of any shape within another polygon of any shape (or conclude that such a solution is not possible).

Answer 1

Probably not.

The bin-packing problem is NP-complete, and any instance of the bin-packing problem can be turned into a 2D packing problem. (Represent each integer $k$ with a $1\times k$ rectangle, and make the bins of size $n$ into several $1\times n$ holes with tiny "channels" connecting them into one full shape.) Therefore the 2D packing problem is at least as hard as the bin-packing problem.