Finding the largest area axis-parallel rectangle in a polygon

Karen Daniels, Victor Milenkoviec, Dan Roth

Research output: Contribution to journalArticlepeer-review

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 non-orthogonal polygons. Using this framework, we show that the LR in a general polygon (allowing holes) can be found in O(n log2 n) time. This matches the running time of the best known algorithm for orthogonal polygons. References are given for the application of the framework to other types of polygons. For each type, the running time of the resulting algorithm matches the running time of the best known algorithm for orthogonal polygons of that type. A lower bound of time in Ω(n log n) 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 log n) and an upper bound of O(n log2 n) for general polygons.

Original languageEnglish (US)
Pages (from-to)125-148
Number of pages24
JournalComputational Geometry: Theory and Applications
Volume7
Issue number1-2
DOIs
StatePublished - Jan 1997

Keywords

  • Fast matrix searching
  • Geometric optimization
  • Rectangles

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Finding the largest area axis-parallel rectangle in a polygon'. Together they form a unique fingerprint.

Cite this