License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.406
URN: urn:nbn:de:0030-drops-51229
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5122/
Balko, Martin ;
Jelínek, Vít ;
Valtr, Pavel ;
Walczak, Bartosz
On the Beer Index of Convexity and Its Variants
Abstract
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 a relationship between these two natural measures of convexity of S.
We show that every subset S of the plane with simply connected components satisfies b(S) <= alpha c(S) for an absolute constant alpha, provided b(S) is defined. This implies an affirmative answer to the conjecture of Cabello et al. asserting 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 S 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 beta(d) > 0 such that every subset S of R^d satisfies b_d(S) <= beta c(S), provided b_d(S) exists. We provide an almost matching lower bound by showing that there is a constant gamma(d) > 0 such that for every epsilon from (0,1] there is a subset S of R^d of Lebesgue measure one satisfying c(S) <= epsilon and b_d(S) >= (gamma epsilon)/log_2(1/epsilon) >= (gamma c(S))/log_2(1/c(S)).
BibTeX - Entry
@InProceedings{balko_et_al:LIPIcs:2015:5122,
author = {Martin Balko and V{\'i}t Jel{\'i}nek and Pavel Valtr and Bartosz Walczak},
title = {{On the Beer Index of Convexity and Its Variants}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {406--420},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-83-5},
ISSN = {1868-8969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5122},
URN = {urn:nbn:de:0030-drops-51229},
doi = {10.4230/LIPIcs.SOCG.2015.406},
annote = {Keywords: Beer index of convexity, convexity ratio, convexity measure, visibility}
}
|
Keywords: |
|
Beer index of convexity, convexity ratio, convexity measure, visibility |
|
Collection: |
|
31st International Symposium on Computational Geometry (SoCG 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
12.06.2015 |
