Peeling potatoes near-optimally in near-linear time

DOI10.1145/2582112.2582159zbMATH Open1395.68293arXiv1406.1368OpenAlexW2963688152MaRDI QIDQ4635546FDOQ4635546

Authors: S. Cabello, Josef Cibulka, Jan Kynčl, Maria Saumell, Pavel Valtr 

Publication date: 23 April 2018

Published in: Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

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-varepsilon)$-approximation algorithm for this problem: in $O(n(lo{g}^{2}n+(1/varepsilo{n}^3)logn+1/varepsilo{n}^4))$ time we find a convex polygon contained in $P$ that, with probability at least $2/3$, has area at least $(1-varepsilon)$ 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$.

Full work available at URL: https://arxiv.org/abs/1406.1368

Recommendations

• Peeling potatoes near-optimally in near-linear time
• A polynomial solution for the Potato-peeling problem
• Finding largest rectangles in convex polygons
• Largest inscribed rectangles in convex polygons
• Peeling meshed potatoes

zbMATH Keywords

approximation algorithmgeometric optimizationgeometric probabilityvisibility graphpotato peeling

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Randomized algorithms (68W20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited In (2)

• Peeling meshed potatoes
• A polynomial solution for the Potato-peeling problem

This page was built for publication: Peeling potatoes near-optimally in near-linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635546)