This is a perfect example of an amazing problem in theoretical computer science -- one of those problems that intrigues you the moment you first hear the premise. It goes like this: given a polygon in a Euclidean plane, compute the Largest-Area Rectangle that can be contained within the given polygon!
There are different variations of the problem, in which we can assume that the given polygon has certain properties, e.g. it may be orthogonal, or convex, or it may be assumed to have holes, versus no holes, etc.
- A Harvard Univerity paper on many variations of the problem
- Another paper on the problem for rectilinear poloygons
Notice that this is one of those problems in which the greedy approach doesn't work: what is the ideal solution "locally" — i.e., within an arbitrary row or column — is not necessarily the optimal choice globally. I intend to add a diagram to illustrate what I mean by this.
Therefore, unless we choose a clever reorganization of the data, we'll need to do some backtracking.