Packing rectangles into convex polygons but without rotations I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps.  In my problem you are not allowed to rotate the rectangles and can assume that they are oriented parallel with the axes. You are just given the dimensions of a rectangle and the vertices of the polygon and asked how many identical copies of the rectangle can be packed into the polygon.  If you are allowed to rotate the rectangles this problem is known to be NP-hard I believe. However, what is known if you cannot? How about if the convex polygon is simply a triangle?  Are there known approximation algorithms if the problem is indeed NP-hard? 

Summary so far (21 March '11). Peter Shor observes that we can regard this problem as one of packing unit squares in a convex polygon and that that problem is in NP if you impose a polynomial bound on the number of squares/rectangles to be packed.  Sariel Har-Peled points out there is a PTAS for the same polynomially bounded case.  However, in general the number of squares packed can be exponential in the size of the input which only consists of a possibly short list of pairs of integers.  The following questions appear to be open.

Is the full unbounded version in NP?
Is there a PTAS for the unbounded version?
Is the polynomially bounded case in P or NPC? And my personal favourite, is the problem any easier if you just restrict yourself to packing unit squares into a triangle?
The problem can be reformulated as picking a maximum number of points inside a convex polygon, such that the every pair of them is in distance (under the $L_\infty$ metric) at least $1$ from each other (just think about the centers of the squares). This in turn is related to the same problem where one uses the regular Euclidean distance. This is in turn related to meshing, where one is interested in breaking a polygon into nicely behaved regions (i.e., you take the Voronoi diagram of the centers [see Centroidal Voronoi tessellations]).

Anyway, a $(1-\epsilon)$-approximation is quite easy. You randomly slide a grid of sidelength $O(1/\epsilon)$. Clip the polygon into the grid, and solve the problem inside each piece of intersection of the polygon with the grid using brute force. An algorithm with running time $O(M*noise(\epsilon))$ should easily follow, where $M$ is the number of points (i.e., rectangles), and $noise(\epsilon)$ is some horrendous function that depends only on $\epsilon$.