Thursday, January 31, 2008

A non-Euclidean characterization of convexity: proof of theorem

We give here the proof of the theorem and corollary stated in "A non-Euclidean characterization of convexity".

Theorem. For any X in Rn

Hwave(X) = X U int(Hconvex(X)),

where Hwave(X) = Ur≥0Br(Br(X) \ Rn) \ Rn, Br(A) is the union of all closed balls of radius r centered at points in A, int(A) is the interior set of A and Hconvex(X) is the convex hull of X.


1. X U int(Hconvex(X)) is included in Hwave(X): obviously X is included in Hwave(X). If x is in int(Hconvex(X)), we can find an n-simplex σ around x that is entirely included in Hconvex(X). From the definition of a convex hull, for each face fi of σ there must be some xi in X such that xi lies in the interior of the half-space delimited by the fi and not including x. Consider now an arbitrary ray h departing from x: h will intersect some face fi in the manner depicted below.

Following the variable naming convention of the figure, if we set r(h) = (a2+bi2)/2a then for any point y in h dist(xi,y) > r(h) → dist(x,y) > r(h). It can be seen that the values r(h) are upper bounded by some r, as we have only finitely many bi's and a is bounded by the diameter of σ; and it follows that x belongs to Br(Br(X) \ Rn) \ Rn, since all points of Rn at a distance greater than r from every point of X must also be farther away than r from x.

2. Hwave(X) is included in X U int(Hconvex(X)): Let x be a point outside X U int(Hconvex(X)). By Hahn-Banach Separation Theorem, there is a hyperplane π separating x from int(Hconvex(X)), which implies that all points of X are included at one of the closed half-spaces delimited by π. Let h be the ray normal to π with origin in π, passing through x and moving away from X.

For any r ≥ 0, the point y in h at distance r from x (in the direction away from X) verifies that dist(x',y) > r for every x' in X U int(Hconvex(X)); this is so even in the case where x belongs to the boundary of Hconvex(X) and hence lies directly on π. So for every r ≥ 0 x is in Br(Br(X) \ Rn) and thus does not belong to Hwave(X).

Corollary. cl(Hconvex(X)) = r>0Hwave(Br(X)), where where cl(A) denotes the topological closure of A.

Proof. If x is in Hconvex(X), then for any r > 0 x is also in int(Br(Hconvex(X)) = int(Hconvex(Br(X)), which is included in Hwave(Br(X)). Conversely, if x does not belong to cl(Hconvex(X)) then by Hahn-Banach Separation Theorem there is a hyperplane separating x and cl(Hconvex(X)), and a fortiori separating x and cl(Hconvex(Br(X))) for some r > 0; but the latter set is a superset of Hwave(Br(X)), hence x does not belong to this either.

No comments :

Post a Comment