Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 Rn. 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.

share|improve this question
add comment

3 Answers

up vote 15 down vote accepted

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.

share|improve this answer
    
Let me mention this recent preprint arxiv.org/abs/math.CO/0701745 which has references to a number of generalizations of the "Tietze-Nakajima theorem". –  Igor Pak Apr 27 '10 at 1:43
    
Note that this place where the first edge touches the boundary could be the endpoint of the first edge. –  Zsbán Ambrus Jun 8 '12 at 18:50
    
@Zsban: you are right, I was not careful in the proof sketch. I'm updating the answer. –  Sergei Ivanov Jun 9 '12 at 5:14
add comment

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.

share|improve this answer
    
Seems like this would still work if you replace $\mathbb{R}^n$ by a Banach space, but the completeness seems to be used in an essential way. Is there a counterexample for an incomplete normed space? –  Nate Eldredge Apr 21 '10 at 17:36
    
Any topological linear space is OK. If a and b are in an open set G and G is connected, you can join them by a broken line. Now just consider the section of G by the finite-dimensional subspace that contains that broken line. –  fedja Apr 21 '10 at 18:48
    
Thanks. You were right about the pre-80's book being the best bet. The Valentine reference that Ivanov pointed out has this and some variations. –  Nathan Reading Apr 22 '10 at 13:02
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.