Largest inscribed rectangles in convex polygons

We consider approximation algorithms for the problem of computing an inscribed rectangle having largest area in a convex polygon on n vertices. If the order of the vertices of the polygon is given, we present a randomized algorithm that computes an inscribed rectangle with area at least (1/ε) times the optimum with probability t in time O(1εlogn) for any constant t<1. We further give a deterministic approximation algorithm that computes an inscribed rectangle of area at least (1-ε) times the optimum in running time O(1 ε2logn) and show how this running time can be slightly improved.

Subjects

Approximation algorithms

Geometric algorithms

Inscribed rectangles in polygons

Largest area rectangle

Options

Largest inscribed rectangles in convex polygons