Tuesday, January 15, 2008

A non-Euclidean characterization of convexity

A set X in a real vector space is convex if for every x, y in X the segment xy = {λx + (1−λ)y : 0 ≤ λ ≤ 1} is included in X. There are ways to extend the concept of convexity from vector spaces to metric spaces based on the translation of the "segment" concept: for instance, a set X in some suitable metric spaces is geodesically convex if for any pair of points x, y in X the geodesic between x and y is also in X. We explore an alternate extension of the concept of convexity that does not involve any kind of segment construct. The following considerations motivate the definition.

Consider some set X in Rn (say R2 for simplicity of display) composed of several irregular components. Imagine now that this set X is made of some radioactive material so that it creates a radiation wavefront propagating from X outwards:

If seen from a sufficiently long distance, the radiation wavefront is indistinguishable from that of a convex set Y with the same exterior shape as X:

So, the convex hull of X (or something very similar to it, as we will see later) can be reconstructed from its radiation wavefront at some distance r by retropropagating the wavefront towards X. Let us see a graphical example where X consists of three points and the wavefront w is considered at a distance r larger than the diameter of X:

Retropropagating w is equivalent to considering the wavefront at distance r generated by the exterior of w:

The resulting shape includes X and approximates the convex hull of X (in this case, the triangle with vertices in X) as r grows. So, we have a characterization of convexity resorting only to our wavefront construction, which can be formalized by means of metric space balls:

Definition. Let S be some metric space and X a set of points in S. The wavefront hull of X, Hwave(X), is defined as

Hwave(X) = Ur≥0Br(Br(X) \ S) \ S,

where Br(A) is defined as the union of all closed balls of radius r centered at points in A.

Theorem. For any X in Rn

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

where int(A) denotes the interior set of A and Hconvex(X) is the convex hull of X.

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

We will prove the theorem and corollary in a later entry.

1 comment :

  1. Ya he visto tu blog, muy interesante.
    Por cierto, el otro día estuve pensando en el teorema López-García de desgajamiento de yogures y se cumple también en las tres dimensiones(nº de cortes = nº total de elementos -1), ponte a ver si sacas la demostración del tema.