To what extent is convexity a local property? - MathOverflow

To what extent is convexity a local property?

2010-04-21T14:42:20Z

A polyhedron is the intersection of a finite collection of halfspaces. These halfspaces are not assumed to be linear, i.e. their bounding hyperplanes are not assumed to contain the origin. The support Supp(M) of a collection M of polyhedra is the union of the polyhedra in M. I can prove the following theorem:

Theorem. Let M be a finite set of n-dimensional polyhedra in Rⁿ. Suppose:
(i) The interior of Supp(M) is path-connected; and
(ii) For every x in the boundary of Supp(M), there exists a closed halfspace H⁺ bounded by a hyperplane H such that x is in H, and such that H⁺ contains every P in M such that x is in P.
Then Supp(M) is convex.

(Acknowledgment: I proved a characterization of coarsenings of a given polyhedral complex and Ezra Miller remarked that part of my argument amounted to some sort of local criterion for convexity. The theorem above is that criterion.)

The point here is that you only need to check, at each point x of the boundary, that Supp(M) looks sufficiently like a convex set near x, and (ii) says exactly what "sufficiently like a convex set" means in this case.

The question is:

Is this a special case of some general theorem that says that convexity is somehow a local condition?

I suspect that I'm asking for a reference to something known. One convexity person that I asked about felt that it is "highly likely..., that this result is a special case of a result in functional analysis, once properly understood." The same person suggested that there might be a connection to the theory of tight manifolds in topology. For that reason I have added the tags fa.functional-analysis and gt.geometric-topology. My apologies if these tags turn out not to be appropriate.

Answer by fedja for To what extent is convexity a local property?

2010-04-21T17:27:57Z

Claim: Suppose that $G$ is a connected bounded open set in $\mathbb R^n$ such that for every $x\in\partial G$, $\exists r>0$ and a half-space $S$ such that $x\in\partial S$ and $G\cap B(x,r)\subset S$. Then $G$ is convex.

Proof:

Step 1. Suppose that $f:G\to \mathbb R$ is a continuous function such that for every $x\in G$, there exists $r>0$ and a linear function $L_x$ satisfying $L_x(x)=f(x)$ and $f(y)<L_x(y)$ for all $y\ne x$ with $|y-x|<r$ . Then $f$ is concave in the sense that if $a,b\in G$ and the whole interval $[a,b]$ is contained in $G$, then $f(ta+(1-t)b)\ge tf(a)+(1-t)f(b)$ for $t\in[0,1]$.

Proof: Suppose not. Then $\min_t[f(ta+(1-t)b)-tf(a)+(1-t)f(b)]<0$ . Take $s\in(0,1)$ to be the point where it is attained and let $x=sa+(1-s)b$. Then the linear function $L_x(ta+(1-t)b)-tf(a)+(1-t)f(b)$ has a strict local minimum at $t=s$, which is impossible.

Step 2. We can replace the strict inequality in the conditions of Step 1 by a nonstrict one keeping the conclusion.

Proof: Just subtract $\delta|x|^2$ with small $\delta>0$.

Step 3: The distance to the boundary function satisfies the conditions of Step 1.

Proof: Let $x\in G$. Let $y$ be the boundary point closest to $x$. Let $r$ and $S$ be the radius and the half-space for $y$. Then $L_x(z)=\text{dist}(z,\partial S)$ and $r$ work for $x$.

Step 4: $G$ is convex.

Proof: Take any 2 points $a,b$ in $G$. Suppose that the interval $[a,b]$ is not contained in $G$. Start moving $b$ towards $a$ along some path connecting them in $G$. Somewhere on the way, you'll get the situation when $a$ and $b$ are deep inside $G$ (that is true all the time) but $[a,b]$ is just barely inside $G$. Then the distance to the boundary dips on $[a,b]$, which is impossible due to the concavity just proved.

The whole thing is certainly well-known and in good old times all of this would be written in most standard calculus textbooks (possibly, as an exercise). Unfortunately, nowadays we have to teach students to add fractions instead. Nevertheless, the textbooks in convex geometry and analysis written before 1980 would be your best bet if you want a reference. I would try something like Rockafellar's "Convex Analysis" to start with.

Answer by Sergei Ivanov for To what extent is convexity a local property?

2010-04-21T18:25:31Z

This is known as Tietze theorem: if $A$ is an open connected set such that for every boundary point there is a locally supporting hyperplane, then $A$ is convex. I don't know what is the standard reference, internet search gave me the following one:

F.A.Valentine. Convex sets. McGraw-Hill, New York, 1964, pp. 51-53.

There are easier proofs than fedja's (at least to geometer's eye). My favorite one is the following. Take $a,b\in A$, there is a polygonal path from $a$ to $b$ in $A$. Suppose this path has $N$ edges. Then there is a shortest polygonal path of at most $N$ edges in the closure of $A$. If it is not a straight segment, the first edge must touch the boundary of $A$ (otherwise one can shorten the path). The first point where it meets the boundary has obvious problems with local supporting hyperplane.

Update. As Zsbán Ambrus pointed out in a comment, vertices on the boundary cause problems, so one should restrict to polygonal paths contained in the interior. But then it is not clear why a minimum exists. Rather that considering a minimum, one can do shorthening by hand: begin with any polygonal path in the interior, choose consecutive serments $[a,b]$ and $[b,c]$ and move $b=b(t)$ to $a$ along the segment. If a segment $[a,b(t)]$ touches the boundary at some moment $t$, observe a contradiction. If not, then the final segment $[a,c]$ is also contained in the interior, so we get a polygonal line with fewer edges. Repeat this procedure until it becomes a single segment.

Answer by unknown (google) for To what extent is convexity a local property?

2012-06-11T08:34:03Z

"Locally convexity implies convexity" holds more generally for CAT(0) spaces. See e.g. Convex rank 1 subsets of Euclidean Buildings Proposition 4.1