Knauer, ChristianChristianKnauerSchlipf, LenaLenaSchlipfSchmidt, Jens M.Jens M.SchmidtTiwary, Hans RajHans RajTiwary2020-10-222020-10-222012-05Journal of Discrete Algorithms (2012)http://hdl.handle.net/11420/7638We 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.en1570-866720127885Approximation algorithmsGeometric algorithmsInscribed rectangles in polygonsLargest area rectangleJournal Article10.1016/j.jda.2012.01.002Other