Technically, given a direction, the extreme points for P can be computed and an enclosing rectangle is therefore constructed. The answer, thankfully, is no.
P has a side collinear with an edge of the polygon.
The above result dramatically restricts the range of possible rectangles. Not only is it not necessary to check all directions, but only as many as the polygon's number of edges. A simple algorithm would be to compute for each edge the corresponding rectangle collinear with it. The entire algorithm would then have quadratic time complexity. A much more efficient algorithm can be found.