Largest inscribed rectangles in convex polygons
- Knauer, Christian
- Schlipf, Lena
- Schmidt, Jens M.
- Tiwary, Hans Raj
DOIAbstract
AbstractWe 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
Add to ORKG