Finding the Maximum Area Parallelogram in a Convex Polygon
Kai Jin, Kevin Matulef · 2011
We consider the problem of finding the maximum area parallelogram (MAP) inside a given convex polygon. Our main result is an algorithm for computing the MAP in an n-sided polygon in O(n2) time. Achieving this running time requires proving several new structural properties of the MAP, and combining them with a rotating technique of Toussaint [10]. We also discuss applications of our result to the problem of computing the maximum area centrallysymmetric convex body (MAC) inside a given convex polygon, and to a “fault tolerant area maximization” problem which we define. 1