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 ? log n ) for any constant t<1 t < 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 ? 2 log n ) and show how this running time can be slightly improved.
approximation algorithms geometric algorithms largest area rectangle inscribed rectangles in polygons