Veröffentlichung

Titel:

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

Abstract:

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(n^3)$. We also give $(1-\epsilon )$-approximation algorithms that take time $O({\epsilon }^{-1/2}\log n+{\epsilon }^{-3/2})$.

Download:

arXiv

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}, }