On the Beer index of convexity and its variants

2017
journal article
article
dc.abstract.enLet S be a subset of R d Rd with finite positive Lebesgue measure. The Beer index of convexityb(S) b(S) of S is the probability that two points of S chosen uniformly independently at random see each other in S. The convexity ratioc(S) 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 set S⊆R 2 S⊆R2 with simply connected components satisfies b(S)⩽αc(S) b(S)⩽αc(S) for an absolute constant α α , provided b(S) 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) b(S) . For 1⩽k⩽d 1⩽k⩽d , the k-index of convexityb k (S) bk(S) of a set S⊆R d S⊆Rd is the probability that the convex hull of a (k+1) (k+1) -tuple of points chosen uniformly independently at random from S is contained in S. We show that for every d⩾2 d⩾2 there is a constant β(d)>0 β(d)>0 such that every set S⊆R d S⊆Rd satisfies b d (S)⩽βc(S) bd(S)⩽βc(S) , provided b d (S) bd(S) exists. We provide an almost matching lower bound by showing that there is a constant γ(d)>0 γ(d)>0 such that for every ε∈(0,1) ε∈(0,1) there is a set S⊆R d S⊆Rd of Lebesgue measure 1 satisfying c(S)⩽ε c(S)⩽ε and b d (S)⩾γεlog 2 1/ε ⩾γc(S)log 2 1/c(S) bd(S)⩾γεlog2⁡1/ε⩾γc(S)log2⁡1/c(S) .pl
dc.affiliationWydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznejpl
dc.contributor.authorBalko, Martinpl
dc.contributor.authorJelínek, Vítpl
dc.contributor.authorValtr, Pavelpl
dc.contributor.authorWalczak, Bartosz - 114113 pl
dc.date.accessioned2017-04-26T09:26:51Z
dc.date.available2017-04-26T09:26:51Z
dc.date.issued2017pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number1pl
dc.description.physical179-214pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume57pl
dc.identifier.doi10.1007/s00454-016-9821-3pl
dc.identifier.eissn1432-0444pl
dc.identifier.issn0179-5376pl
dc.identifier.urihttp://ruj.uj.edu.pl/xmlui/handle/item/39720
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa 3.0 Polska*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/pl/legalcode*
dc.share.typeinne
dc.subject.enBeer index of convexitypl
dc.subject.enconvexity ratiopl
dc.subject.enconvexity measurepl
dc.subject.envisibilitypl
dc.subtypeArticlepl
dc.titleOn the Beer index of convexity and its variantspl
dc.title.journalDiscrete and Computational Geometrypl
dc.typeJournalArticlepl
dspace.entity.typePublication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
0
Views per month