Finding largest rectangles in convex polygons

Abstract

We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with n vertices. We give exact algorithms that solve these problems in time O(n(3)). We also give (1 - epsilon)-approximation algorithms that take time O(epsilon(-1/2) log n + epsilon(-3/2)).