%0 Journal Article
%T Peeling potatoes near-optimally in near-linear time
%A Sergio Cabello
%A Josef Cibulka
%A Jan Kyn£¿l
%A Maria Saumell
%A Pavel Valtr
%J Mathematics
%D 2014
%I arXiv
%X We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon $P$ with $n$ vertices. We give a randomized near-linear-time $(1-\varepsilon)$-approximation algorithm for this problem: in $O((n/\varepsilon^4) \log^2 n \log(1/\delta))$ time we find a convex polygon contained in $P$ that, with probability at least $1-\delta$, has area at least $(1-\varepsilon)$ times the area of an optimal solution.
%U http://arxiv.org/abs/1406.1368v1