Finding an axis-aligned rectangle inside a polygon

I am looking for a good algorithm to find an axis-aligned rectangle inside a (not necessarily convex) polygon. A maximal rectangle would be nice, but is not necessary - any algorithm that can find a "fairly good" rectangle would be fine.

The polygon may also have holes, but any pointers to algorithms that only work for convex or simple polygons would be helpful too.

In my implementation, intersection testing for sides is fairly cheap, but "point in polygon" tests are expensive, so ideally should be minimised.