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(n3). We also give (1ε)-approximation algorithms that take time O(ε1/2logn+ε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}, }
Christoph Doppelbauer | 10.05.2024