Logo der Fakultät Logo LG Theoretische Informatik



Finding largest rectangles in convex polygons

AutorInnen: Sergio Cabello
Otfried Cheong
Christian Knauer
Lena Schlipf
Kategorie: Artikel in Zeitschriften
erschienen in: Computational Geometry, Vol. 51, 2016, pp. 67-74

We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with n vertices. We give exact algorithms that solve these problems in time O(n3). We also give (1ε)-approximation algorithms that take time O(ε1/2logn+ε3/2).

Download: DOI Ressource
BibTeX-Eintrag: @article{, author = {Sergio Cabello and Otfried Cheong and Christian Knauer and Lena Schlipf}, title = {Finding largest rectangles in convex polygons}, journal = {Comput. Geom.}, volume = {51}, pages = {67--74}, year = {2016}, url = {http://dx.doi.org/10.1016/j.comgeo.2015.08.001}, doi = {10.1016/j.comgeo.2015.08.001}, }
Christoph Doppelbauer | 05.05.2017
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen