On the Beer Index of Convexity and Its Variants

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10331064" target="_blank" >RIV/00216208:11320/17:10331064 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/article/10.1007%2Fs00454-016-9821-3" target="_blank" >http://link.springer.com/article/10.1007%2Fs00454-016-9821-3</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00454-016-9821-3" target="_blank" >10.1007/s00454-016-9821-3</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Beer Index of Convexity and Its Variants

Popis výsledku v původním jazyce

Let S be a subset of R^d with finite positive Lebesgue measure. The Beer index of convexity b(S) of S is the probability that two points of S chosen uniformly independently at random see each other in S. The convexity ratio c(S) of S is the Lebesgue measure of the largest convex subset of S divided by the Lebesgue measure of S. We investigate the relationship between these two natural measures of convexity. We show that every subset of R^2 with simply connected components satisfies b(S)⩽αc(S) for an absolute constant α, provided b(S) is defined. This implies an affirmative answer to the conjecture of Cabello et al. that this estimate holds for simple polygons. We also consider higher-order generalizations of b(S). For 1⩽k⩽d, the k-index of convexity b_k(S) of a subset of R^d is the probability that the convex hull of a (k+1)-tuple of points chosen uniformly independently at random from S is contained in S. We show that for every d⩾2 there is a constant β(d)&gt;0 such that every subset of R^d satisfies b_d(S)⩽βc(S), provided b_d(S) exists. We provide an almost matching lower bound by showing that there is a constant γ(d)&gt;0 such that for every ε from (0,1) there is a subset of R^d of Lebesgue measure 1 satisfying c(S)⩽ε and b_d(S)⩾γε/ log(1/ε)⩾γc(S)/log(1/c(S)). .

Název v anglickém jazyce

On the Beer Index of Convexity and Its Variants

Popis výsledku anglicky

Let S be a subset of R^d with finite positive Lebesgue measure. The Beer index of convexity b(S) of S is the probability that two points of S chosen uniformly independently at random see each other in S. The convexity ratio c(S) of S is the Lebesgue measure of the largest convex subset of S divided by the Lebesgue measure of S. We investigate the relationship between these two natural measures of convexity. We show that every subset of R^2 with simply connected components satisfies b(S)⩽αc(S) for an absolute constant α, provided b(S) is defined. This implies an affirmative answer to the conjecture of Cabello et al. that this estimate holds for simple polygons. We also consider higher-order generalizations of b(S). For 1⩽k⩽d, the k-index of convexity b_k(S) of a subset of R^d is the probability that the convex hull of a (k+1)-tuple of points chosen uniformly independently at random from S is contained in S. We show that for every d⩾2 there is a constant β(d)&gt;0 such that every subset of R^d satisfies b_d(S)⩽βc(S), provided b_d(S) exists. We provide an almost matching lower bound by showing that there is a constant γ(d)&gt;0 such that for every ε from (0,1) there is a subset of R^d of Lebesgue measure 1 satisfying c(S)⩽ε and b_d(S)⩾γε/ log(1/ε)⩾γc(S)/log(1/c(S)). .

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA14-14179S" target="_blank" >GA14-14179S: Algoritmické, strukturální a složitostní aspekty konfigurací v rovině</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete and Computational Geometry

ISSN

0179-5376

e-ISSN

—

Svazek periodika

57

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

36

Strana od-do

179-214

Kód UT WoS článku

000393700500009

EID výsledku v databázi Scopus

2-s2.0-84987660664