Number of the records: 1

# Peeling Potatoes Near-optimally in Near-linear Time

1. 1.
0478998 - ÚI 2018 RIV US eng J - Journal Article
Cabello, S. - Cibulka, J. - Kynčl, J. - Saumell, Maria - Valtr, P.
Peeling Potatoes Near-optimally in Near-linear Time.
Siam Journal on Computing. Roč. 46, č. 5 (2017), s. 1574-1602. ISSN 0097-5397. E-ISSN 1095-7111
R&D Projects: GA ČR GBP202/12/G061
Grant - others:GA MŠk(CZ) LO1506; GA MŠk(CZ) EE2.3.30.0038
Institutional support: RVO:67985807
Keywords : geometric optimization * potato peeling * visibility graph * geometric probability * approximation algorithm
Subject RIV: BA - General Mathematics
OBOR OECD: Pure mathematics
Impact factor: 0.902, year: 2017

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( \log^2 n + (1/\varepsilon^3) \log n + 1/\varepsilon^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 area of the largest convex body inside $P$ to the probability that two points chosen uniformly at random inside $P$ are mutually visible. 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$.