Peeling potatoes near-optimally in near-linear time

DOI10.1145/2582112.2582159MaRDI QIDQ4635546zbMATH OpenOpenAlexFDO

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)

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

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)

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$.

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

Cited in

(3)

• Peeling meshed potatoes
• Peeling potatoes near-optimally in near-linear time
• 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)