Finding the Maximum Area Axis-parallel Rectangle in a Polygon.
Karen Daniels, Victor Milenkovic, Dan Roth · 1993
We consider the geometric optimization problem of finding the maximum area axis-parallel rectangle (MAAPR) in an n-vertex general polygon. We characterize the MAAPR for general polygons by considering different cases based on the types of contacts between the rectangle and the polygon. We present a general framework for solving a key subcase of the MAAPR problem which dominates the running time for a variety of polygon types. Using this framework, we obtain the following MAAPR time results: \\Theta(n) for xy-monotone polygons, O(nff(n)) for orthogonally convex polygons, O(nff(n) log n) for horizontally (vertically) convex polygons, (where ff(n) is the slowly growing inverse of Ackermann's function), O(n log n) for a special type of horizontally convex polygon, and O(n log 2 n) for general polygons. For all these types of non-rectilinear polygons, we match the running time of the best known algorithms for their rectilinear counterparts. We prove a lower bound of time in \\Omega\\Gamma n ...