On the Beer Index of Convexity and Its Variants

详细信息    查看全文

• 作者：Martin Balko ; Vít Jelínek ; Pavel Valtr…
• 关键词：Beer index of convexity ; Convexity ratio ; Convexity measure ; Visibility
• 刊名：Discrete & Computational Geometry
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：57
• 期：1
• 页码：179-214
• 全文大小：873KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Computational Mathematics and Numerical Analysis;
• 出版者：Springer US
• ISSN：1432-0444
• 卷排序：57

文摘

Let S be a subset of \(\mathbb {R}^d\) with finite positive Lebesgue measure. The Beer index of convexity\({\text {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\({\text {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\subseteq \mathbb {R}^2\) with simply connected components satisfies \({\text {b}}(S)\leqslant \alpha {\text {c}}(S)\) for an absolute constant \(\alpha \), provided \({\text {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 \({\text {b}}(S)\). For \(1\leqslant k\leqslant d\), the k-index of convexity\({\text {b}}_k(S)\) of a set \(S\subseteq \mathbb {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\geqslant 2\) there is a constant \(\beta (d)>0\) such that every set \(S\subseteq \mathbb {R}^d\) satisfies \({\text {b}}_d(S)\leqslant \beta {\text {c}}(S)\), provided \({\text {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 \(\varepsilon \in (0,1)\) there is a set \(S\subseteq \mathbb {R}^d\) of Lebesgue measure 1 satisfying \({\text {c}}(S)\leqslant \varepsilon \) and \({\text {b}}_d(S)\geqslant \gamma \frac{\varepsilon }{\log _2{1/\varepsilon }}\geqslant \gamma \frac{{\text {c}}(S)}{\log _2{1/{\text {c}}(S)}}\).