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/2log⁡n+ε−3/2)$.