Finding the largest axis aligned rectangle in a polygon in o(n log n) time.
Ralph P. Boland, Jorge Urrutia · 2001
We consider the problem of nding the largest area axis-aligned rectangle contained in an n vertex polygon. We present an algorithm that solves this problem in O(n log n) time. This is an improvement by a factor of O(log n) over the best known algorithm. Our method of achieving this improvement is noteworthy. The previous algorithm constructs a cover of the polygon by a collection of subpolygons, of the type we call SAM polygons, such that any rectangle in the polygon is contained in one of the SAM subpolygons. This cover requires O(n log n) time and space to construct. Our algorithm also constructs a cover of the polygon by SAM subpolygons such that any rectangle in the polygon is contained in one of the subpolygons but does so using only linear time and space. 1