Finding the largest rectangle in several classes of polygons

DSpace/Manakin Repository

Finding the largest rectangle in several classes of polygons

Citable link to this page


Title: Finding the largest rectangle in several classes of polygons
Author: Daniels, Karen; Milenkovic, Victor; Roth, Dan

Note: Order does not necessarily reflect citation order of authors.

Citation: Daniels, Karen, Victor J. Milenkovic, and Dan Roth. 1995. Finding the largest rectangle in several classes of polygons. Harvard Computer Science Group Technical Report TR-22-95.
Full Text & Related Files:
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.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search