Finding Largest Rectangles in Convex Polygons

Autor:	Cabello, Sergio, Cheong, Otfried, Knauer, Christian, Schlipf, Lena
Rok vydání:	2014
Předmět:	Computer Science - Computational Geometry
Druh dokumentu:	Working Paper
Popis:	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-\varepsilon)$-approximation algorithms that take time $O(\varepsilon^{-3/2}+ \varepsilon^{-1/2} \log n)$. Comment: The time bound to approximate the maximum-perimeter rectangle is improved. Christian Knauer becomes coauthor
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1405.1223 Zobrazit plný text záznamu View this record from Arxiv