Peeling potatoes near-optimally in near-linear time

Abstract

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-\epsilon )$-approximation algorithm for this problem: in $O(n({\log }^{2}n+(1/{\epsilon }^3)\log n+1/{\epsilon }^4))$ time we find a convex polygon contained in $P$ that, with probability at least $2/3$, has area at least $(1-\epsilon )$ times the area of an optimal solution. We also obtain similar results for the variant of computing a convex polygon inside $P$ with maximum perimeter. To achieve these results we provide new results in geometric probability. The first result is a bound relating the probability that two points chosen uniformly at random inside $P$ are mutually visible and the area of the largest convex body inside $P$. The second result is a bound on the expected value of the difference between the perimeter of any planar convex body $K$ and the perimeter of the convex hull of a uniform random sample inside $K$.

30 pages, 7 figures; minor revision. Preliminary version was presented at SoCG 2014

References in corpus (1)

• On the Beer index of convexity and its variants