Simple view
Full metadata view
Authors
Statistics
On the Beer index of convexity and its variants
Beer index of convexity
convexity ratio
convexity measure
visibility
Let 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)⩾γεlog21/ε⩾γc(S)log21/c(S)
.
dc.abstract.en | Let 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)⩾γεlog21/ε⩾γc(S)log21/c(S) . | pl |
dc.affiliation | Wydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznej | pl |
dc.contributor.author | Balko, Martin | pl |
dc.contributor.author | Jelínek, Vít | pl |
dc.contributor.author | Valtr, Pavel | pl |
dc.contributor.author | Walczak, Bartosz - 114113 | pl |
dc.date.accessioned | 2017-04-26T09:26:51Z | |
dc.date.available | 2017-04-26T09:26:51Z | |
dc.date.issued | 2017 | pl |
dc.date.openaccess | 0 | |
dc.description.accesstime | w momencie opublikowania | |
dc.description.number | 1 | pl |
dc.description.physical | 179-214 | pl |
dc.description.version | ostateczna wersja wydawcy | |
dc.description.volume | 57 | pl |
dc.identifier.doi | 10.1007/s00454-016-9821-3 | pl |
dc.identifier.eissn | 1432-0444 | pl |
dc.identifier.issn | 0179-5376 | pl |
dc.identifier.uri | http://ruj.uj.edu.pl/xmlui/handle/item/39720 | |
dc.language | eng | pl |
dc.language.container | eng | pl |
dc.rights | Udzielam licencji. Uznanie autorstwa 3.0 Polska | * |
dc.rights.licence | CC-BY | |
dc.rights.uri | http://creativecommons.org/licenses/by/3.0/pl/legalcode | * |
dc.share.type | inne | |
dc.subject.en | Beer index of convexity | pl |
dc.subject.en | convexity ratio | pl |
dc.subject.en | convexity measure | pl |
dc.subject.en | visibility | pl |
dc.subtype | Article | pl |
dc.title | On the Beer index of convexity and its variants | pl |
dc.title.journal | Discrete and Computational Geometry | pl |
dc.type | JournalArticle | pl |
dspace.entity.type | Publication |