On the Beer index of convexity and its variants

DOI10.1007/S00454-016-9821-3MaRDI QIDQ512263zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Martin Balko, Vít Jelínek, Pavel Valtr, Bartosz Walczak

Publication date 24 February 2017

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1412.1769

zbMATH Keywords

visibilityBeer index of convexityconvexity measureconvexity ratio

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Approximation by convex sets (52A27)

Abstract: Let $S$ be a subset of $mathbb{R}^d$ with finite positive Lebesgue measure. The Beer index of convexity $operatornameb(S)$ of $S$ is the probability that two points of $S$ chosen uniformly independently at random see each other in $S$. The convexity ratio $operatornamec(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 $Ssubseteqmathbb{R}^2$ with simply connected components satisfies $operatornameb(S)leqalphaoperatornamec(S)$ for an absolute constant $alpha$, provided $operatornameb(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 $operatornameb(S)$. For $1leqkleqd$, the $k$-index of convexity $operatorname{b}_k(S)$ of a set $Ssubseteqmathbb{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 $dgeq2$ there is a constant $$ such that every set $Ssubseteqmathbb{R}^d$ satisfies $$, provided $operatorname{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 $varepsilonin(0,1)$ there is a set $Ssubseteqmathbb{R}^d$ of Lebesgue measure $1$ satisfying $operatornamec(S)leqvarepsilon$ and $operatorname{b}_d(S)geqgammafracvarepsilonlo{g}_{2}1/varepsilongeqgammafracoperatornamec(S)lo{g}_{2}1/operatornamec(S)$.

Recommendations

• On the Beer index of convexity and its variants
• Approximations of convex bodies by measure-generated sets
• scientific article; zbMATH DE number 653182
• A bound on a convexity measure for point sets

Cites work

• scientific article; zbMATH DE number 1022658 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3033300 (Why is no real title available?)
• scientific article; zbMATH DE number 3052220 (Why is no real title available?)
• A note on the measurability of convex sets
• Approximation of convex bodies by inscribed simplices of maximum volume
• Continuity properties of the visibility function
• Elements of combinatorial and differential topology. Transl. from the Russian by Olga Sipacheva
• On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato
• Peeling potatoes near-optimally in near-linear time
• Piercing quasi-rectangles-on a problem of Danzer and Rogers
• Polygonal entropy: A convexity measure
• The index of convexity and parallel bodies
• The index of convexity and the visibility function
• Unsolved problems in geometry
• Weak -nets for points on a hypersphere
• -nets and simplex range queries

Cited in

(4)

• The convexification effect of Minkowski summation
• Peeling potatoes near-optimally in near-linear time
• Displacement Lipschitz spaces and rectifiability
• On the Beer index of convexity and its variants

This page was built for publication: On the Beer index of convexity and its variants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q512263)