Finding the largest rectangle in several classes of polygons

Abstract

This paper considers the geometric optimization problem of finding the Largest area axis-parallel Rectangle (LR) in an n-vertex general polygon. We characterize the LR for general polygons by considering different cases based on the types of contacts between the rectangle and the polygon. A general framework is presented for solving a key subproblem of the LR problem which dominates the running time for a variety of polygon types. This framework permits us to transform an algorithm for orthogonal polygons into an algorithm for nonorthogonal polygons. Using this framework, we obtain the following LR time results: ϴ(n) for xy-monotone polygons, O(nα(n)) for orthogonally convex polygons, (where α(n) is the slowly growing inverse of Ackermann's function), O(nα(n)logn) for horizontally (vertically) convex polygons, O(n(logn)) for a special type of horizontally convex polygon (whose boundary consists of two y-monotone chains on opposite sides of a vertical line), and O(n(log^2n)) for general polygons (allowing holes). For all these types of non-orthogonal polygons, we match the running time of the best known algorithms for their orthogonal counterparts. A lower bound of time Ω(n(logn)) is established for finding the LR in both self-intersecting polygons and general polygons with holes. The latter result gives us both a lower bound of Ω(n(logn)) and an upper bound of O(n(log^2n)) for general polygons.