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?