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−ϵ)(1−ϵ) times the optimum with probability t   in time O(1ϵlogn) for any constant t<1t<1. We further give a deterministic approximation algorithm that computes an inscribed rectangle of area at least (1−ϵ)(1−ϵ) times the optimum in running time O(1ϵ2logn) and show how this running time can be slightly improved.