4
$\begingroup$

What methods exist to quantify convexity. Yes, a set is convex if the the line between two points in the set is contained in the set, but is there a measure of how convex a set is? If so, what is it?

$\endgroup$

3 Answers 3

3
$\begingroup$

Indeed there are notions which say "how convex" (at least) the unit ball with respect to some norm is. First, there is the notion of uniform convexity. This basically says that the connecting line between two points on the boundary has to be strictly inside the body.

More refined notions can be gained from the modulus of convexity of the unit ball with respect to some norm. This basically measures how far inside the midpoint between two points on the boundary lies inside the unit ball depending on the distance of these two points. In formula: The modulus of convexity of a norm $\|\cdot\|$ is the function $$ \delta(\epsilon) = \inf\{1 - \frac{\|x-y\|}{2}\ |\ \|x\|=\|y\| = 1,\ \|x-y\|\geq\epsilon\}. $$ The slower $\delta$ tends to zero for $\epsilon\to 0$, the "more convex" the unit ball is.

As an example: For the unit ball for the 1-norm or the supremum norm, it holds $\delta(\epsilon) = 0$ for small $\epsilon$ and hence, these are not very convex things. If I remember correctly, for the two norm (or for any Hilbert space) it holds that $\delta(\epsilon) = 1 - \sqrt{1 - \epsilon^2/4}$ which is quadratic in $\epsilon = 0$, i.e. $\delta(\epsilon) = O(\epsilon^2)$. This is the slowest behavior possible.

I think that one could extend this notion to other convex sets with some effort but I don't know if this has been done.

Many books on Banach spaces and their geometry treat such topics.

$\endgroup$
3
$\begingroup$

You could in principle compare the set with its convex hull, which is a superset, and with its convex kernel, which is a subset. To quantify, you could compare area and volumes. I don't know any references for this approach, though.

Google found these papers, which may get your started:

$\endgroup$
5
  • $\begingroup$ Since every convex set coincides with its convex hull and with its convex kernel, it seems difficult to use these notions to quantify how convex a convex set is (irrespective of the way one interprets the phrase how convex). $\endgroup$
    – Did
    Jan 18, 2012 at 11:56
  • $\begingroup$ @DidierPiau, the OP wants to quantify how convex a set is, not how convex a convex set is. $\endgroup$
    – lhf
    Jan 18, 2012 at 11:58
  • $\begingroup$ OK. $ $ $ $ $ $ $\endgroup$
    – Did
    Jan 18, 2012 at 12:00
  • $\begingroup$ @lhf I am familiar with the convex hull. What is the convex kernel? $\endgroup$
    – analysisj
    Jan 18, 2012 at 12:58
  • $\begingroup$ @analysisj, the convex kernel of a set is the subset of point that see every point in the set. $\endgroup$
    – lhf
    Jan 18, 2012 at 14:00
0
$\begingroup$

A set is either convex or not. However, one can try to measure how "symmetric" a convex set is. A classic paper about this is "Measures of Symmetry for Convex Sets" by Branko Grünbaum, pg. 233-270,in Convexity, Proceedings of Symposia in Pure Mathematics, Vol. VII, 1963, editor Victor Klee.

$\endgroup$
4
  • 1
    $\begingroup$ Saying that a set is either convex or not is like saying that every event has probability 0.5 because it will either happen or not... $\endgroup$
    – lhf
    Jan 18, 2012 at 11:59
  • $\begingroup$ @lhf: given that the first assertion is true and the second is false, I am failing to see much commonality between them... $\endgroup$ Jan 18, 2012 at 13:37
  • 2
    $\begingroup$ @Pete, you're right, of course. I meant that just because convexity is a sharp concept it does not follow that it doesn't make sense to ask how convex a set is. $\endgroup$
    – lhf
    Jan 18, 2012 at 13:59
  • 1
    $\begingroup$ I really really appreciate thinking like @lhf and not thinking like Pete or Joseph. It's like "how even is a number" can be measured with p-adic norms, but asking Pete or Joseph "how even is a number," you'd just get the answer "a number is even or it's not." This seems like an extremely myopic and closed minded answer. $\endgroup$ Feb 29, 2020 at 10:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .