On the Beer index of convexity and its variants

DOI10.1007/S00454-016-9821-3zbMATH Open1416.60020DBLPjournals/dcg/BalkoJVW17arXiv1412.1769OpenAlexW3105989876WikidataQ59609912 ScholiaQ59609912MaRDI QIDQ512263FDOQ512263

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

Publication date: 24 February 2017

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

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)$.

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

Recommendations

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

zbMATH Keywords

visibilityBeer index of convexityconvexity measureconvexity ratio

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(\epsilon\)-nets and simplex range queries
• Title not available (Why is that?)
• Unsolved problems in geometry
• A note on the measurability of convex sets
• Elements of combinatorial and differential topology. Transl. from the Russian by Olga Sipacheva
• Weak \(\varepsilon\)-nets for points on a hypersphere
• Piercing quasi-rectangles-on a problem of Danzer and Rogers
• On the largest convex polygon contained in a non-convex n-gon, or how to peel a potato
• The index of convexity and parallel bodies
• Continuity properties of the visibility function
• The index of convexity and the visibility function
• Polygonal entropy: A convexity measure
• Peeling Potatoes Near-Optimally in Near-Linear Time
• Approximation of convex bodies by inscribed simplices of maximum volume

Cited In (3)

• The convexification effect of Minkowski summation
• Peeling Potatoes Near-Optimally in Near-Linear Time
• Displacement Lipschitz spaces and rectifiability

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)