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 }^{-3/2}+{\epsilon }^{-1/2}\log n)$.

The time bound to approximate the maximum-perimeter rectangle is improved. Christian Knauer becomes coauthor