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 Rⁿ

H_wave(X) = X U int(H_convex(X)),

where H_wave(X) = U_r≥0B_r(B_r(X) \ Rⁿ) \ Rⁿ, B_r(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 H_convex(X) is the convex hull of X.

Proof.

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

Following the variable naming convention of the figure, if we set r(h) = (a²+b_i²)/2a then for any point y in h dist(x_i,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 b_i's and a is bounded by the diameter of σ; and it follows that x belongs to B_r(B_r(X) \ Rⁿ) \ Rⁿ, since all points of Rⁿ at a distance greater than r from every point of X must also be farther away than r from x.

2. H_wave(X) is included in X U int(H_convex(X)): Let x be a point outside X U int(H_convex(X)). By Hahn-Banach Separation Theorem, there is a hyperplane π separating x from int(H_convex(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(H_convex(X)); this is so even in the case where x belongs to the boundary of H_convex(X) and hence lies directly on π. So for every r ≥ 0 x is in B_r(B_r(X) \ Rⁿ) and thus does not belong to H_wave(X).

Corollary. cl(H_convex(X)) = ∩_r>0H_wave(B_r(X)), where where cl(A) denotes the topological closure of A.

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