Počet záznamů: 1  

Peeling Potatoes Near-optimally in Near-linear Time

  1. 1.
    SYSNO ASEP0478998
    Druh ASEPJ - Článek v odborném periodiku
    Zařazení RIVJ - Článek v odborném periodiku
    Poddruh JČlánek ve WOS
    NázevPeeling Potatoes Near-optimally in Near-linear Time
    Tvůrce(i) Cabello, S. (SI)
    Cibulka, J. (CZ)
    Kynčl, J. (CZ)
    Saumell, Maria (UIVT-O) RID, SAI, ORCID
    Valtr, P. (CZ)
    Zdroj.dok.Siam Journal on Computing - ISSN 0097-5397
    Roč. 46, č. 5 (2017), s. 1574-1602
    Poč.str.29 s.
    Jazyk dok.eng - angličtina
    Země vyd.US - Spojené státy americké
    Klíč. slovageometric optimization ; potato peeling ; visibility graph ; geometric probability ; approximation algorithm
    Vědní obor RIVBA - Obecná matematika
    Obor OECDPure mathematics
    CEPGBP202/12/G061 GA ČR - Grantová agentura ČR
    Institucionální podporaUIVT-O - RVO:67985807
    UT WOS000416763900004
    EID SCOPUS85032943193
    DOI10.1137/16M1079695
    AnotaceWe 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$.
    PracovištěÚstav informatiky
    KontaktTereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
    Rok sběru2018