January 4, 2001

Lectures on Geometry

Christer O. Kiselman

Contents:

1. Introduction

2. Closure operators and Galois correspondences 3. Convex sets and functions

4. Infimal convolution

5. Convex duality: the Fenchel transformation 6. The Monge–Kantorovich problem

7. The Brunn–Minkowski inequality

8. Non-convex sets

9. Notions of topology

10. Smallest neighborhood spaces

11. Digital Jordan curve theorems References

1. Introduction

These notes comprise the main part of a course presented at Uppsala University in the Fall of 1999. (The original name of the course was Geometry and Analysis.) My initial idea was to present duality in geometry, or how to use analysis to solve geometric problems. This I did, not dodging the more difficult aspects of this duality—see Theorems 5.10 and 5.11 and the nasty Examples 5.7–5.9 and 5.12. A natural application was Kantorovich’s theorem, to which I found a new proof (Theorem 6.1). Also duality of sets which are not convex was considered (Section 8). Finally, my interest in image analysis led me to an attempt to survey some results in digital geometry; since existing proofs of Khalimsky’s Jordan curve theorem turned out to be difficult to present, I tried to find a simple one, which appears now in Section 11.

I am grateful to Björn Ivarsson for valuable criticism of an early draft of Section 2; to Thomas Kaijser for sharing his knowledge on the Monge–Kantorovich problem; and to Ingela Nyström and Erik Palmgren for helpful comments on an early version of Section 11.

2. Closure operators and Galois correspondences

An order relation in a set X is a relation (a subset of X^{2}) which satisfies three conditions: it is reflexive, antisymmetric and transitive. This means, if we denote the relation by ⩽, that for all x, y, z ∈ X,

(2.1)  x ⩽ x;

(2.2)  x ⩽ y and y ⩽ x implies x = y;

(2.3)  x ⩽ y and y ⩽ z implies x ⩽ z.

An ordered set is a set X together with an order relation. (Sometimes one says partially ordered set.)

A basic example is the set P (W) of all subsets of a set W, with the order relation given by inclusion, thus A ⩽ B being defined as A ⊂ B for A, B ∈ P (W).

A closure operator in an ordered set X is a mapping X ∋ x ↦ \overline{x} ∈ X which is expanding, increasing (or order preserving), and idempotent; in other words, which satisfies the following three conditions for all x, y ∈ X:

(2.4)  x ⩽ \overline{x};
(2.5)  x ⩽ y implies \overline{x} ⩽ \overline{y};
(2.6)  \overline{\overline{x}} = \overline{x}.

In checking (2.6) it is of course enough to prove that \overline{\overline{x}} ⩽ \overline{x} if we have already proved (2.4).

The element \overline{x} is said to be the closure of x. Elements x such that \overline{x} = x are called closed (for this operator). An element is closed if and only if it is the closure of some element (and then it is the closure of itself).

A basic example of a closure operator is of course the topological closure operator which associates to a set in a topological space its topological closure, i.e., the smallest closed set containing the given set. In fact a closure operator in P (W) defines a topology in W if and only if it satisfies, in addition to (2.4), (2.5), (2.6) above, two extra conditions, viz. that \overline{Ø} = Ø and

(2.7)  \overline{A ∪ B} = \overline{A} ∪ \overline{B} for all A, B ⊂ W.

Another closure operator of great importance is the operator which associates to a set in R^{n} its convex hull, the smallest convex set containing the given set.

In both these examples X is the power set of some set W, and the closure operator is given as an intersection:

\overline{A} = ⋂(Y; Y is closed and Y ⊃ A).

More generally, if a closure operator x ↦ \overline{x} is given and we denote by F the set of its closed elements, then

(2.8)  \overline{x} = inf(y ∈ F; y ⩾ x).

Conversely, any subset F of X such that the infimum of a subset of F always exists defines a closure operator by formula (2.8).

A Galois correspondence is a pair (f, g) of two decreasing mappings f: X → Y, g: Y → X of two given ordered sets X, Y such that g ∘ f and f ∘ g are expanding. In other words we have f(x_{1}) ⩾ f(x_{2}) and g(y_{1}) ⩾ g(y_{2}) if x_{1} ⩽ x_{2} and y_{1} ⩽ y_{2}, and g(f(x)) ⩾ x and f(g(y)) ⩾ y for all x ∈ X, y ∈ Y; Kuroš [1962:6:11].

The name Galois correspondence alludes to the first correspondence of that kind, established by Galois^{1} with X as the subsets of a field, Y as the sets of isomorphisms of this field, f(x) as the group of all isomorphisms leaving all elements of x invariant, and g(y) as the subfield the elements of which are left fixed by all elements of y.

1Évariste Galois, 1811–1832.

Proposition 2.1. Let f: X → Y, g: Y → X be a Galois correspondence. Then g ∘ f: X → X and f ∘ g: Y → Y are closure operators. Moreover, f ∘ g ∘ f = f and g ∘ f ∘ g = g.

Proof. That g ∘ f and f ∘ g are expanding is part of the definition of a Galois correspondence; that they are increasing follows from the fact that they are compositions of two decreasing mappings. We know that f ∘g is expanding, so (f ∘g)(f(x)) ⩾ f(x); thus f ∘ g ∘ f ⩾ f. On the other hand, also g ∘ f is expanding, i.e., g ∘ f ⩾ id_{X}, so f ∘ g ∘ f ⩽ f ∘ id_{X} = f, hence f ∘ g ∘ f = f. By symmetry, g ∘ f ∘ g = g. From either one of these identities we easily obtain that g ∘ f and f ∘ g are idempotent.

It is now natural to ask whether the closure operators one obtains from Galois correspondences have some special property. The answer is no: every closure operator comes in a trivial way from some Galois correspondence.

Proposition 2.2. Let x ↦ \overline{x} be a closure operator defined in an ordered set X. Then there exist an ordered set Y and a Galois correspondence f: X → Y, g: Y → X such that \overline{x} = g(f(x)) for all x ∈ X.

Proof. We define Y as the set of all closed elements in X with the opposite order, thus y_{1} ⩽_{Y} y_{2} shall mean that y_{1} ⩾_{X} y_{2}. Let f: X → Y and g: Y → X be defined by f(x) = \overline{x} and g(y) = y. Then both f and g are decreasing, and g ∘ f(x) = \overline{x} ⩾_{X} x, f ∘ g(y) = y ⩾_{Y} y. So g ∘ f and f ∘ g are expanding, and \overline{x} = g(f(x)) as desired.

This proposition is, in a sense, completely uninteresting. This is because the Galois correspondence is obtained from X and the closure operator in a totally trivial way. However, there are many Galois correspondences in mathematics that are highly interesting and represent a given closure operator. This is because they allow for important calculations to be made or for new insights into the theory.

We now ask whether the composition of two closure operators is a closure operator. Example. Let A be the set of all points (x, y) in R^{2} satisfying y ⩾ 1/(1 + x^{2}). This is a closed set, so \overline{A} = A if we let the bar denote topological closure. The convex hull of A is the set cvx A = {(x, y) ∈ R^{2}; y > 0}, which is not closed; its closure is \overline{cvx A} = \{(x, y); y ⩾ 0\}. Hence we see that it is not true that the convex hull of a closed set is closed; on the other hand we shall see that the closure of a convex set is convex. Define f(A) = cvx A and g(A) = \overline{A}. Then the composition h = g ∘ f is a closure operator, whereas the other composition k(A) = f ∘ g(A) = cvx \overline{A} defines a mapping k = f ∘ g which is not a closure operator (k ∘ k ≠ k).

Proposition 2.3. Let f, g: X → X be two closure operators. The following properties are equivalent:

(i) g ∘ f is a closure operator; (ii) g ∘ f is idempotent; (iii) g ∘ f ∘ g = g ∘ f; (iv) f ∘ g ∘ f = g ∘ f;

(v) g(x) is f-closed if x is f-closed. If one of these conditions is satisfied, then g ∘ f is the supremum of the two closure operators f and g in the ordered set of all closure operators; moreover f ∘ g ⩽ g ∘ f.

Proof. That h = g ∘ f is expanding and increasing is true for any composition of expanding and increasing mappings, so it is clear that (i) and (ii) are equivalent. It is also easy to see that (iv) and (v) are equivalent. If (iii) holds, then h ∘ h = g ∘ f ∘ g ∘ f = g ∘ f ∘ f = g ∘ f = h, so h is idempotent. Similarly, (iv) implies (ii). Conversely, if (ii) holds, then

g ∘ f ⩽ g ∘ f ∘ g ⩽ h ∘ h = h = g ∘ f

and

g ∘ f ⩽ f ∘ g ∘ f ⩽ h ∘ h = h = g ∘ f,

so we must have equality all the way in both chains of inequalities, which proves that (iii) and (iv) hold. The last statement is easy to verify.

Corollary 2.4. Two closure operators f and g commute if and only if both g ∘f and f ∘ g are closure operators.

Proof. If g ∘ f = f ∘ g, then (iii) obviously holds, so g ∘ f is a closure operator. Conversely, if g ∘ f is a closure operator, then (iii) applied to f and g says that g ∘ f ∘ g = g ∘ f; if also f ∘ g is a closure operator, then (iv) applied to g and f says that g ∘ f ∘ g = f ∘ g. Thus f and g commute.

When two closure operators f and g are given, it may happen that f ⩽ g. Then the semigroup generated by f and g consists of at most three elements, id_{X}, f, g. If both g ∘ f and f ∘ g are closure operators, then the semigroup generated by f and g has at most four elements, id_{X}, f, g, and g ∘ f = f ∘ g. If precisely one of g ∘ f and f ∘ g is a closure operator, then the semigroup generated has exactly five elements, id_{X}, f, g, g ∘ f, and f ∘ g, of which four are closure operators. When none of g ∘ f and f ∘ g is a closure operator, the semigroup of all compositions f_{m} ∘ ⋯ ∘ f_{1}, with f_{j} = f or f_{j} = g, m ∈ N, may be finite or infinite.

Applying Proposition 2.3 to the case f(A) = cvx A, g(A) = \overline{A} we see that the operation of taking the topological closure of the convex hull, A ↦ \overline{cvx A} is a closure operator. We call \overline{cvx A} the closed convex hull of A. This is a case where the semigroup generated by f and g consists of five elements.

Example. Let E be a finite-dimensional vector space over R and let E^{∗} denote its dual. (We can think of R^{n}, but it is often clarifying to distinguish E and its dual.) We shall define a Galois correspondence: the ordered set X shall be the power set of E, the set of all subsets of E, with inclusion as the order, and the set Y = [−∞, +∞]^{E^{∗}} shall be the set of all functions with values in the extended real line and defined on the dual of E, the order being the opposite of the usual order, defined by set inclusion of the epigraphs, so that φ ⩽_{Y} ψ iff φ(ξ) ⩾ ψ(ξ) for all ξ ∈ E^{∗}; see Definition 3.10. Thus the constant +∞ is the smallest function, corresponding to vacuum, while −∞ is the largest element, corresponding to an infinitely dense neutron star. We define mappings f: X → Y and g: Y → X as follows. Let H_{A} denote the supporting function of a subset A of E, i.e.,

H_{A}(ξ) = sup_{x∈A} ξ(x), ξ ∈ E^{∗}.

Let f(A) = H_{A}. To any function φ on E^{∗} with values in the extended real line [−∞, +∞] = R ∪ {−∞, +∞} we associate a set

g(φ) = ⋂_{ξ∈E^{∗}}{x; ξ(x) ⩽ φ(ξ)}.

It is an intersection of closed half-spaces (including possibly the whole space and the empty set). Then both f and g are decreasing, and g ∘ f and f ∘ g are expanding as shown by the formulas

(g ∘ f)(A) = ⋂_{ξ∈E^{∗}}{x ∈ E; ξ(x) ⩽ H_{A}(ξ)} ⊃ A for all setsA,
(f ∘ g)(φ) = H_{g(φ)} ⩾_{Y} φ for all functions φ.

This is a highly interesting Galois correspondence. We shall determine its closed elements in Section 5.

3. Convex sets and functions

Given two points a, b in a vector space E we define the segment between a and b as the set

[a, b] = {(1 − t)a + tb; 0 ⩽ t ⩽ 1}.

A subset A of E is said to be convex if it contains the whole segment [a, b] as soon it contains a and b. The convex subsets of the real line are precisely the intervals. The definition can therefore be given as follows: for any affine mapping φ: R → E the inverse image φ^{−1}(A) shall be an interval.

The notion of a convex set has a sense in affine spaces, which, roughly speaking, are like vector spaces without a determined origin. In affine spaces sums like ∑ λ_{j}x_{j} have a sense if and only if ∑ λ_{j} = 1, which is the case in the sums we need to work with when considering convexity. If under this hypothesis we perform a translation by a vector a, then form the sum, and finally perform a translation by the vector −a, we get a result independent of the translation. Indeed, ∑ λ_{j}(x_{j} − a) + a = ∑ λ_{j}x_{j}.

The convex hull of a set X is the set

(3.1)  cvx X = ⋂_{Y} (Y; Y is convex and contains X) ;

cf. (2.8). It is clear that cvx X is convex and that it is the smallest convex set containing X.

The description (3.1) of the convex hull is a description from the outside: we approach the hull by convex sets containing it. There is also a description from within:

Theorem 3.1. Let X be any subset of a vector space E. Then cvx X is the set of all linear combinations ∑_{j=1}^{N} λ_{j}x_{j}, where N is an arbitrary integer ⩾ 1, where the points x_{j} belong to X, and where the coefficients λ_{j} satisfy λ_{j} ⩾ 0, ∑ λ_{j} = 1. The proof of this proposition is left to the reader; cf. Hiriart-Urruty & Lemaréchal [1993: Prop. 1.3.4], Kiselman [1991a or b: Theorem 2.1], or Rockafellar [1970: Theorem 2.3].

The linear combinations that occur in the proposition are called convex combinations. (The requirement that N be at least 1 is important; thanks to this requirement we obtain that the convex hull of the empty set is empty.)

Theorem 3.2 (Carathéodory’s^{2} theorem). Let X and E be as in Theorem 3.1 and assume that E is of finite dimension n. Then it is enough to take N in the representation equal to n + 1. For the proof of this result see Kiselman [1991a or b: Theorem 6.1] or Rockafellar [1970: Theorem 17.1]. In one and two dimensions, maybe even three, it is intuitively obvious.

Corollary 3.3. The convex hull of a compact subset of R^{n} is compact.

Proof. It is clear that for N = 1, 2, ... the set

K_{N} = { ∑_{1}^{N} λ_{j}x_{j}; λ_{j} ⩾ 0, ∑_{1}^{N} λ_{j} = 1}

is compact, for it is the continuous image of a compact set under a continuous mapping. In general, the convex hull of K is the union of all the K_{N}, N ⩾ 1. But thanks to Carathéodory’s theorem, the sequence is stationary and the union of the sequence is equal to K_{n+1}.

Theorem 3.4. The closure of a convex set in a topological vector space is convex; more generally, this is true in a vector space E equipped with a topology such that all translations x ↦ x − a, a ∈ E, and all dilations x ↦ λx, λ ∈ R, are continuous.

Proof. Suppose that A is convex and let a_{0}, a_{1} ∈ \overline{A}. We have to prove that [a_{0}, a_{1}] ⊂ \overline{A}. Consider a = (1 − t)a_{0} + ta_{1} for an arbitrary fixed t ∈ [0, 1], and let V be an arbitrary neighborhood of a. Then we can choose a neighborhood V_{0} of a_{0} such that (1 − t)V_{0} + ta_{1} ⊂ V. Since a_{0} belongs to the closure of A, there exists a point b_{0} ∈ A ∩ V_{0}. Next we can find a neighborhood V_{1} of a_{1} such that (1 − t)b_{0} + tV_{1} ⊂ V. There exists a point b_{1} ∈ A∩V_{1}. Hence the linear combination (1−t)b_{0} +tb_{1} belongs to A and since it also belongs to V, we have proved that V intersects A, thus that a ∈ \overline{A}.

Thanks to this theorem we can state that \overline{cvx X} is the smallest closed and convex set which contains X. The set is called the closed convex hull of X.

We shall now study the possibility of separating two convex sets by a hyperplane. A hyperplane is an affine subspace of codimension one; in other words it consists

of all solutions to a single linear equation ξ(x) = b, where ξ is a nonzero linear form on the space and where b is a real number. In general we need to distinguish between a general hyperplane, defined by a not necessarily continuous linear form on the one hand, and a closed hyperplane, defined by a continuous linear form on the other hand. However, we shall restrict attention here to finite-dimensional spaces equipped with the unique separated vector space topology—when in the sequel we consider a finite-dimensional vector space we shall always assume that it carries this topology. For these finite-dimensional spaces all linear forms are continuous and all affine subspaces closed. To every hyperplane we associate two closed half-spaces, D_{+} = {x; ξ(x) ⩾ b} and D_{−} = {x; ξ(x) ⩽ b}. There is a choice to be made here, since −ξ(x) = −b defines the same hyperplane as ξ(x) = b.

We shall say that a hyperplane H = {x; ξ(x) = b} separates two subsets X and Y of E if ξ(x) ⩽ b ⩽ ξ(y) for all x ∈ X and all y ∈ Y. We shall say that H separates X and Y strictly if we have ξ(x) < b < ξ(y) for all x ∈ X and all y ∈ Y.

2Constantin Carathéodory, 1873–1950.

Theorem 3.5. Let F be a closed convex subset of a finite-dimensional vector space E, and y ∈ E a point which does not belong to F Then there exists a hyperplane which separates F and y strictly, even in the strong sense that for some numbers b_{0}, b_{1} we have ξ(x) < b_{0} < b < b_{1} < ξ(y) for all x ∈ F.

Theorem 3.6. Let A be a convex subset of a finite-dimensional vector space E, and y ∈ E a point which does not belong to A or which belongs to the boundary of A. Then there exists a hyperplane which separates A and y.

Theorem 3.7. Let F and K be closed convex subsets of a finite-dimensional vector space E, and assume that they are disjoint and that K is compact. Then there exists a hyperplane which separates F and K strictly, even in the strong sense that for some numbers b_{0}, b_{1} we have ξ(x) < b_{0} < b < b_{1} < ξ(y) for all x ∈ F and all y ∈ K.

Theorem 3.8. Let X and Y be convex subsets of a finite-dimensional vector space E, and assume that they are disjoint. Then there exists a hyperplane which separates X and Y.

Proof of Theorem 3.5. We may assume that y = 0. If F = Ø the result is certainly true, so we may assume that F is nonempty. Let d = inf_{x∈F} ∥x∥, where we use a Euclidean norm. Then d is positive, since F is closed, and d < +∞, since F is nonempty. Moreover, there exists a point a in (the possibly unbounded set) F where the infimum is attained. This is because the infimum over all of F is the same as the infimum over the compact set K = {x ∈ F; ∥x∥ ⩽ 2d}. I claim that a · x ⩾ ∥a∥^{2} for all x ∈ F. Study the function f(t) = ∥(1 − t)a + tx∥^{2}, where x is a point in F. We must have f′(0) ⩾ 0, for if f′(0) were negative, f(t) would be smaller than f(0) = d^{2} for small positive t contrary to the definition of d and a; note that all points (1 − t)a + tx with t ∈ [0, 1] belong to F. Now it is easy to calculate f′:

f′(t) = −2(1 − t)∥a∥^{2} − 2ta · x + 2(1 − t)a · x + 2t∥x∥^{2};

in particular f′(0) = −2∥a∥^{2} + 2a · x. Since this quantity has to be nonnegative, we must have a · x ⩾ a · a as claimed. Any hyperplane a · x = b with 0 < b < a · a is now strictly separating. Proof of Theorem 3.6. Let (a_{j})_{j∈N} be a sequence which is dense in A. We apply Theorem 3.5 to the compact set F_{m} = cvx{a_{0}, ..., a_{m}}, m ∈ N. If y does not belong to A, it does not belong to F_{m} either. If y belongs to the boundary of A, it may belong to A, and some care is needed to avoid that y belongs to F_{m}. We can choose y_{m} ∉ A such that y_{m} tends to y and apply Theorem 3.5 to F_{m} and y_{m}.

For every m there is a hyperplane ξ_{m}(x) = b_{m} which separates y_{m} and F_{m}. We may assume that ∥ξ_{m}∥ = 1. Then the sequence (b_{m}) is also bounded, so there are subsequences (ξ_{m_{j}})_{j} and (b_{m_{j}})_{j} which converge to limits ξ and b respectively. The hyperplane ξ(x) = b separates y from A. Proof of Theorem 3.7. The set F − K is closed and does not contain the origin. If ξ(x) = b is a hyperplane which separates the origin from F − K in the strong sense indicated in Theorem 3.5, we know that 0 = ξ(0) < b_{0} < b < b_{1} < ξ(x − y) for all x ∈ F and all y ∈ K, so that

b_{1} ⩽ inf_{x∈F,y∈K}(ξ(x − y)) = inf_{x∈F} ξ(x) − sup_{y∈K} ξ(y),

implying that sup_{K} ξ + b_{1} ⩽ inf_{F} ξ, an inequality which proves the theorem. Proof of Theorem 3.8. We observe that if X and Y are as in the theorem, then A = X − Y does not contain the origin. We apply Theorem 3.6 and argue as in the proof of Theorem 3.7.

An immediate consequence of Theorem 3.5 is that every closed convex set is equal to the intersection of all the closed half-spaces which contain it. But the proof actually gives more: the half-spaces used to form the intersection can all be chosen so that their boundaries contain a point of the given set. More precisely, we considered the largest open ball B(y, r) with center at y ∉ F which does not meet F and found that there is a unique point a common to its closure and F; the tangent plane to the ball at a is a separating hyperplane. A supporting half-space of a set A is a half-space D such that its boundary H (a hyperplane) contains a point of A. We also say in this situation that H is a supporting hyperplane of A. Sometimes, to a given separating hyperplane there is a parallel hyperplane which is supporting, but not always: Example. The set {(x, y) ∈ R^{2}; x > 0, xy ⩾ 1} is convex, and the hyperplane H = {(x, y); x = 0} lies in its complement, but there is no supporting hyperplane parallel to H.

Theorem 3.9. Every closed convex set in a finite-dimensional vector space is equal to an intersection of closed, supporting half-spaces.

Proof. We just have to note that the half-space D = {x; x · a ⩾ a · a} found in the proof of Theorem 3.5 is indeed a supporting half-space: the point a lies both in F and the hyperplane which bounds D.

Definition 3.10. Let f: X → [−∞, +∞] be a function defined on an arbitrary set X. Then its epigraph is the subset of X × R defined as

epi f = {(x, t) ∈ X × R; t ⩾ f(x)}.

The strict epigraph is the set

epi_{s} f = {(x, t) ∈ X × R; t > f(x)}.

Definition 3.11. A function f: X → [−∞, +∞] defined on a subset X of a vector space E is said to be convex if its epigraph is a convex set in E × R. It is equivalent to require that the strict epigraph be convex. We shall use the notation CVX(X) for the set of all convex functions defined in a set X ⊂ E and with values in the extended real line [−∞, +∞].

If we extend f to a function g defined in all of E by putting g(x) equal to +∞ outside X we see that the extended function is convex at the same time as f, since the two functions have the same epigraph. Therefore we may always assume (if we like) that convex functions are defined in the whole space.

The constants +∞ and −∞ are convex, since their epigraphs are, respectively, Ø and all of E. Furthermore, the maximum max(f_{1}, ..., f_{m}) of finitely many convex functions is convex, since its epigraph is the intersection of the convex sets epi f_{j}.

However, if we want to prove for instance that the sum of two convex functions is convex, it is convenient to have an inequality to test: the inequality which says that the graph hangs below the chord. Since convex functions may assume both +∞ and −∞ as values, we must handle undefined sums like (+∞)+(−∞). It is convenient to introduce upper addition + · and lower addition + · . These operations are extensions of the usual addition R × R ∋ (x, y) ↦ x + y ∈ R. We define without hesitation (+∞) + (+∞) = +∞, (−∞) + (−∞) = −∞, and use these definitions for both + · and + · . In the ambiguous cases we define

(3.2)  (+∞) + · (−∞) = +∞,  (+∞) + · (−∞) = −∞.

Upper addition defines an upper semicontinuous function [−∞, +∞]^{2} → [−∞, +∞], and, similarly, lower addition a lower semicontinuous mapping.

Very useful rules for computing infima and suprema are

(3.3)  inf_{x∈X}(a + · f(x)) = a + · inf_{x∈X} f(x),  sup_{x∈X}(a + · f(x)) = a + · sup_{x∈X} f(x),

which are valid without exception. The proof of (3.3) consists in checking the equalities for a = +∞, −∞ and X empty.

Proposition 3.12. Let E be a vector space. A function f: E → [−∞, +∞] is convex if and only if

f((1 − t)x_{0} + tx_{1}) ⩽ (1 − t)f(x_{0}) + · tf(x_{1})

for all x_{0}, x_{1} ∈ E and all numbers t with 0 < t < 1. We leave the simple proof as an exercise.

The proposition implies that the values of a convex function must satisfy an infinity of inequalities, and in general that means that the values are severely restricted. However, note that this is not always the case. As an example consider a function which is +∞ for ∥x∥ > 1 and −∞ for ∥x∥ < 1. Such a function is convex irrespective of its values on the unit sphere ∥x∥ = 1. This phenomenon is related to the fact that all sets A containing the open unit ball and contained in the closed unit ball are convex. (Of course in these examples we need Euclidean norms, or at least strictly convex norms.) We shall exploit this phenomenon in Section 8.

The effective domain of a function f: X → [−∞, +∞] is the set where it is smaller than plus infinity:

(3.4)  dom f = {x ∈ X; f(x) < +∞}.

If f is convex, so is its effective domain.

Theorem 3.13. Let E be a finite-dimensional vector space, let f: E → [−∞, +∞] be a convex function and define Ω = (dom f)^{∘}. (Thus Ω is the interior of the set where the function is less than plus infinity.) Then Ω is convex and the restriction of f to Ω is either equal to the constant −∞ or else a real-valued continuous function. We leave the proof as an exercise. See Kiselman [1991a or b, Theorem 9.5].

Corollary 3.14. Let f and Ω be as in the theorem and suppose that there exists a point x ∈ Ω such that f(x) is real. Then there exists a linear functional ξ on E such that ξ(x) ⩽ f(x) for all x ∈ E. Moreover, g(x) = lim inf_{y→x} f(y) is convex and does not take the value −∞ if f > −∞. We have g = f except on ∂Ω. In analogy with (3.1) we define the convex hull of a function as the largest convex minorant of the function:

(3.5)  cvx f = sup(g ∈ CVX(E); g ⩽ f).

This is the approach from below. There is also an approach from above, as in Theorem 3.1:

Theorem 3.15. Let f: E → [−∞, +∞] be any function on a vector space E. Then its convex hull is given as an infimum of linear combination of values of f:

(3.6) cvx f(x) = inf [ ∑_{1}^{N} λ_{j}f(x_{j}); N ⩾ 1, λ_{j} > 0, ∑_{1}^{N} λ_{j} = 1, ∑_{1}^{N} λ_{j}x_{j} = x], x ∈ E.

The proof is analogous to that of Theorem 3.1.

When f is positively homogeneous, i.e., f(tx) = tf(x) for all t > 0 and all x ∈ E, then (3.6) can be simplified to

(3.7)  cvx f(x) = inf [ ∑_{1}^{N} f(x_{j}); N ⩾ 1, ∑_{1}^{N} x_{j} = x],  x ∈ E.

4. Infimal convolution

Definition 4.1. Let G be an abelian group and let f, g: G → [−∞, +∞] be two functions defined on G and with values in the extended real axis. Then their infimal convolution f ⊓ ⊔ g is defined by

(4.1)  (f ⊓ ⊔ g)(x) = inf_{y∈G} (f(y) + · g(x − y)) ,  x ∈ G.

Often we take G = R^{n}, but it is important to note that the definition works in any abelian group G. In image analysis Z^{2} and, more generally, Z^{n} are very common groups.

Points outside dom f and dom g play no role in (4.1). This is in accordance with the interpretation already mentioned of the constant +∞ as vacuum and of −∞ as an infinitely dense neutron star. Think of e^{−f} as a particle—there is an interesting analogy between infimal convolution of f and g and ordinary convolution of e^{−f} and e^{−g}; see Kiselman [1999a or b, Chapters 8 and 9].

Infimal convolution generalizes vector addition (Minkowski addition) of sets. If X and Y are subsets of G we have

(4.2)  i_{X} ⊓ ⊔ i_{Y} = i_{X+Y} ,

where i_{X} denotes the indicator function of the set X; it takes the value 0 in X and +∞ in its complement.

Another important relation to vector addition—a relation which can actually serve to define infimal convolution—is

(4.3)  epi_{s}(f ⊓ ⊔ g) = epi_{s}(f) + epi_{s}(g),

where the plus sign denotes vector addition in G × R. This equation leads to a geometric interpretation of infimal convolution.

For a thorough study of infimal convolution, see Strömberg [1996].

Proposition 4.2. The infimal convolution is commutative and associative.

Proof. Since vector addition is commutative and associative, the same is true for infimal convolution in view of (4.3).

Thanks to this proposition we can define generally f_{1} ⊓ ⊔ ⋯ ⊓ ⊔ f_{m}; no parantheses are needed. It is easy to see that

(4.4)  dom(f_{1} ⊓ ⊔ ⋯ ⊓ ⊔ f_{m}) = dom f_{1} + ⋯ + dom f_{m}.

Example. The function i_{{0}} is the neutral element for infimal convolution: f ⊓ ⊔ i_{{0}} = f for all functions f. Example. If g: G → R is additive, then f ⊓ ⊔ g = g + C for some constant C = C_{f,g} ∈ [−∞, +∞]. Actually C_{f,g} = (f ⊓ ⊔ g)(0). Example. Define g_{k}(x) = k∥x∥ on a normed space E with norm ∥·∥, with k a positive constant. Study the infimal convolution f_{k} = f ⊓ ⊔ g_{k}. Assuming that f is bounded we see that f_{k} is Lipschitz continuous. Moreover f_{k} ↗ f as k → +∞ if f is bounded and lower semicontinuous.

Let us say that a function f: G → [−∞, +∞] is subadditive if it satisfies the inequality f(x + y) ⩽ f(x) + · f(y), x, y ∈ G.

Proposition 4.3. A function f: G → [−∞, +∞] defined on an abelian group G is subadditive if and only if it satisfies the inequality f ⊓ ⊔ f ⩾ f. If in addition we assume that f(0) ⩽ 0, then this is equivalent to f ⊓ ⊔ f = f.

Proof. If f is subadditive we have f(x − y) + · f(y) ⩾ f(x), so taking the infimum over all y ∈ G gives f ⊓ ⊔ f ⩾ f. Conversely, we have

f(x) + · f(y) ⩾ (f ⊓ ⊔ f)(x + y),

so f ⊓ ⊔ f ⩾ f implies subadditivity. Finally, since the inequality (f ⊓ ⊔ f)(x) ⩽ f(x) + · f(0) always holds, we conclude that f(0) ⩽ 0 implies f ⊓ ⊔ f ⩽ f.

Theorem 4.4. If f and g are subadditive, then so is f ⊓ ⊔ g.

Proof. Using the associativity and commutativity of infimal convolution we can write

(f ⊓ ⊔ g) ⊓ ⊔ (f ⊓ ⊔ g) = (f ⊓ ⊔ f) ⊓ ⊔ (g ⊓ ⊔ g) ⩾ f ⊓ ⊔ g.

Subadditive functions are of interest because of their relation to metrics on abelian groups, a fact which we shall discuss now.

Let us call a function d: X × X → R a distance if it is positive definite, i.e., for all x, y ∈ X,

d(x, y) ⩾ 0 with equality precisely when x = y,

and symmetric, i.e.,

d(x, y) = d(y, x), x, y ∈ X.

We shall say that a distance is a metric if it satisfies in addition the triangle inequality, i.e.,

d(x, z) ⩽ d(x, y) + d(y, z), x, y, z ∈ X.

If X = G is an abelian group, translation-invariant distances are of interest, i.e., those that satisfy

d(x − a, y − a) = d(x, y), a, x, y ∈ G.

Lemma 4.5. Any translation-invariant distance on an abelian group G defines a function f(x) = d(x, 0) on G which is positive definite,

f(x) ⩾ 0 with equality precisely when x = 0;

and symmetric,

f(−x) = f(x), x ∈ X.

Conversely, a function f which is positive definite and symmetric defines a translation-invariant distance d(x, y) = f(x − y). The proof is easy.

Lemma 4.6. Let d be a translation-invariant distance on an abelian group G and f(x) = d(x, 0). Then d is a metric if and only if f is subadditive,

f(x + y) ⩽ f(x) + f(y), x, y ∈ G.

Proof. If d is a metric, we can write, using the triangle inequality and the translation invariance,

f(x + y) = d(x + y, 0) ⩽ d(x + y, y) + d(y, 0) = d(x, 0) + d(y, 0) = f(x) + f(y).

Conversely, if f is subadditive,

d(x, z) = f(x − z) ⩽ f(x − y) + f(y − z) = d(x, y) + d(y, z).

Theorem 4.7 (Kiselman [1996]). Let F: G → [0, +∞] be a function on an abelian group G satisfying F (0) = 0. Define a sequence of functions (F_{j})_{j=1}^{∞} by putting F_{1} = F and F_{j} = F_{j−1} ⊓ ⊔ F, j = 2, 3, ... . Then the sequence (F_{j}) is decreasing and its limit lim F_{j} = f is subadditive. Moreover dom f = N · dom F, i.e., f is finite precisely in the semigroup generated by dom F.

Proof. That the sequence is decreasing is obvious if we take y = 0 in the definition of F_{j+1}:

F_{j+1}(x) = inf_{y}(F_{j}(x − y) + F (y)) ⩽ F_{j}(x) + F (0) = F_{j}(x).

Next we shall prove that f(x + y) ⩽ f(x) + f(y). If one of f(x) and f(y) is equal to +∞, there is nothing to prove, so let us assume that f(x), f(y) < +∞ and let us fix a positive number ε. Then there exists numbers j and k such that F_{j}(x) ⩽ f(x) + ε and F_{k}(y) ⩽ f(y) + ε. By associativity F_{j+k} = F_{j} ⊓ ⊔ F_{k}, so we get

f(x + y) ⩽ F_{j+k}(x + y) ⩽ F_{j}(x) + F_{k}(y) ⩽ f(x) + f(y) + 2ε.

Since ε is arbitrary, the inequality f(x+y) ⩽ f(x)+f(y) follows. The last statement follows from (4.4).

In image analysis it is customary to define distances between adjacent points and then extend the definition to arbitrary pairs of points by going on a path, assigning to each path the sum of the distances between the adjacent points, and finally taking the infimum over all paths. In the translation-invariant case, this amounts to assigning values to a function F at finitely many points, and then define the distance by the function f = lim F_{j} of Theorem 4.7. (Of course some extra conditions are needed to ensure that the limit is symmetric and positive definite.) Indeed the paths consists of segments [0, x^{1}], [x^{1}, x^{1} + x^{2}],..., [x + ⋯ + x^{k−1}, x] and we evaluate the sum F (x^{1}) + F (x^{2}) + ⋯ + F (x^{k}) for all possible choices of x^{1}, ..., x^{k} with sum x.

Examples of such functions are the following. We always define F (0) = 0 and let F (x) < +∞ for x in a finite set P only. The following distances have been studied, assuming P and F to be invariant under permutation and reflection of the coordinates. If we take P = {x ∈ Z^{2}; ∑ |x_{j}| ⩽ 1} and F (1, 0) = 1 we get the cityblock distance, also called l^{1}. If we let P = {x ∈ Z^{2}; |x_{j}| ⩽ 1} and F (1, 0) = F (1, 1) = 1 we get the chess-board metric, or l^{∞} distance. Other choices are F (1, 0) = a, F (1, 1) = b with (a, b) = (1, \sqrt{2}), (2, 3), (3, 4). We can also increase the size of P and define G(1, 0) = 5, G(1, 1) = 7, G(2, 1) = 11. For references to the work mentioned here see Kiselman [1996].

Proposition 4.8. Let f: E → [−∞, +∞] be a function defined on a vector space E and define f_{s} by f_{s}(x) = sf(x/s), x ∈ E, s ∈ R ∖ {0}. Then f is convex if and only if f_{s} ⊓ ⊔ f_{t} ⩾ f_{s+t} for all s, t > 0, and if and only if f_{s} ⊓ ⊔ f_{t} = f_{s+t} for all s, t > 0.

Proof. We note that the inequality f_{s} ⊓ ⊔ f_{t} ⩽ f_{s+t} always holds, so the two last properties are indeed equivalent, and the convex functions are those that satisfy the functional equation f_{s} ⊓ ⊔ f_{t} = f_{s+t}; in other words the mapping s ↦ f_{s} is a homomorphism of semigroups.

If f is convex, we can write

f_{s}(y) + · f_{t}(x − y) = sf(y/s) + · tf((x − y)/t) ⩾ (s + t)f(\frac{y}{s + t} + \frac{x − y}{s + t} ) = f_{s+t}(x).

If we now vary y we obtain f_{s} ⊓ ⊔ f_{t} ⩾ f_{s+t}. Conversely, suppose that this inequality holds. Then we obtain, writing x_{t} = (1 − t)x_{0} + tx_{1}, that

f(x_{t}) = f_{1}(x_{t}) ⩽ (f_{1−t} ⊓ ⊔ f_{t})(x_{t}) ⩽ f_{1−t}(y) + · f_{t}(x_{t} − y)

for every y. We now choose y = (1 − t)x_{0} and get

f(x_{t}) ⩽ f_{1−t}((1 − t)x_{0}) + · f_{t}(x_{t} − (1 − t)x_{0}) = (1 − t)f(x_{0}) + · tf(x_{1}),

which means that f is convex.

Theorem 4.9. If f and g are convex, then so is f ⊓ ⊔ g.

Proof. It is easy to verify that (f ⊓ ⊔ g)_{s} = f_{s} ⊓ ⊔ g_{s}. We now perform a calculation like that in the proof of Theorem 4.4:

(f ⊓ ⊔ g)_{s} ⊓ ⊔ (f ⊓ ⊔ g)_{t} = (f_{s} ⊓ ⊔ g_{s}) ⊓ ⊔ (f_{t} ⊓ ⊔ g_{t}) = (f_{s} ⊓ ⊔ f_{t}) ⊓ ⊔ (g_{s} ⊓ ⊔ g_{t})
⩾ f_{s+t} ⊓ ⊔ g_{s+t} = (f ⊓ ⊔ g)_{s+t}.

Thus f ⊓ ⊔ g satisfies the criterion of Proposition 4.8 and so is convex.

For a positively homogeneous function convexity is equivalent to subadditivity. This observation will yield a nice formula for the supporting function of the intersection of two closed convex sets, see formula (5.9). Here we note the following easy result.

Proposition 4.10. Let f, g be two positively homogeneous convex functions. Then f ⊓ ⊔ g is the convex hull of their minimum:

(4.5)  cvx(min(f, g)) = f ⊓ ⊔ g.

Proof. We always have f ⊓ ⊔ g ⩽ f, f ⊓ ⊔ g ⩽ g since f(0), g(0) ⩽ 0. If h is convex and positively homogeneous and h ⩽ f, g, then h = h ⊓ ⊔ h ⩽ f ⊓ ⊔ g. Thus f ⊓ ⊔ g is the largest positively homogeneous convex minorant of min(f, g). However, it is easy to see that it is also the largest convex minorant of min(f, g), whence (4.5).

5. Convex duality: the Fenchel transformation

The affine functions x ↦ ξ(x) + c, where ξ is a linear form and c a real constant, are the simplest convex functions. It is natural to ask whether all convex functions can be somehow represented in terms of these simple functions. The question is analogous to the problem of representing an arbitrary function in Fourier analysis in terms of the simplest functions, the pure oscillations. The Fenchel transformation, which we shall introduce now, plays a role in convexity theory analogous to that of the Fourier transformation in Fourier analysis.

More precisely we ask whether, given a function f on a vector space E, there exists a subset A of E^{∗} × R such that

(5.1)  f(x) = sup_{(ξ,c)∈A} (ξ(x) + c),  x ∈ E.

Here E^{∗} denotes the algebraic dual of E, i.e., the vector space of all linear forms on E. We first note that if this is at all possible, then c ⩽ f(x) − ξ(x) for all x ∈ E and all (ξ, c) ∈ A, so that c ⩽ inf_{x∈E}(f(x) − ξ(x)). For reasons which will be apparent in a moment, it is convenient to consider instead −c; we must have −c ⩾ sup_{x∈E}(ξ(x) − f(x)) for all (ξ, c) ∈ A. We define

(5.2)  f̃(ξ) = sup_{x∈E} (ξ(x) − f(x)),  ξ ∈ E^{∗}.

The function f̃ is called the Fenchel^{3} transform of f. Other names are the Legendre^{4} transform of f and the function conjugate to f. Since the constant c in (5.1) must satisfy c ⩽ −f̃(ξ), and since f(x) ⩾ ξ(x) − f̃(ξ) for all x ∈ E and all ξ ∈ E^{∗}, we can conclude that (5.1) implies

f(x) = sup_{ξ∈E^{∗}} (ξ(x) − f̃(ξ)), x ∈ E.

In other words, the supremum in (5.1) does not change if we add points outside A and replace c everywhere by −f̃(ξ).

Now the right-hand side of this formula looks like (5.2), so it is natural to apply the transformation a second time. It is convenient here to consider an arbitrary vector subspace F of E^{∗}, and to introduce topologies on E and F as follows. There is a weakest topology on E such that all elements of F are continuous; this is denoted by σ(E, F). There is similarly a weakest topology σ(F, E) on F such that all evaluation mappings F ∋ ξ ↦ ξ(x), x ∈ E, are continuous. We may for instance choose F = E^{∗}, or F = E′, the topological dual of E under a given topology, i.e., the space of all continuous linear forms on E. Actually E^{∗} is the topological dual of E equipped with the topology σ(E, E^{∗}). Thus, when we speak about the topological dual in the sequel, the case of the algebraic dual is always included as a special case. If E is finite-dimensional and we equip it with the separated vector space topology, then E′ = E^{∗}. If E is a normed space of infinite dimension, we always have E′ ≠ E^{∗}. It is not necessary that E and F be in duality; we may even choose F = {0}.

The Fenchel transform of a function g on F is of course a function on the algebraic dual F^{∗} of F:

(5.3)  g̃(X) = sup_{ξ∈F} (X(ξ) − g(ξ)),  X ∈ F^{∗}.

Given any element x of E we define an element X of F^{∗} by the formula X(ξ) = ξ(x), ξ ∈ F. Using this idea we may define for any function g on F,

(5.4)  g̃(x) = sup_{ξ∈F} (ξ(x) − g(ξ)),  x ∈ E.

We also note that f ⊓ ⊔ ξ is an affine function and that in fact (f ⊓ ⊔ ξ)(x) = ξ(x) − f̃(ξ) for all x ∈ E and all ξ ∈ E^{∗}. The function f ⊓ ⊔ ξ is a minorant of f and in fact the largest affine minorant of f which has linear part equal to ξ. So the supremum of all affine minorants of f with linear part in F is

sup_{ξ∈F}(ξ(x) − f̃(ξ)) = sup_{ξ∈F}(f ⊓ ⊔ ξ)(x) = ˜ f̃(x), x ∈ E.

3Werner Fenchel, 1905–1988. 4Adrien Marie Legendre, 1752–1833.

The question whether (5.1) holds for A = F × R can therefore be formulated

very succintly: is it true that ˜ f̃ = f? However, it might still be of interest to find a smaller A for which (5.1) holds.

From the definition of f̃ we immediately obtain the inequality

(5.5)  ξ(x) ⩽ f(x) + · f̃(ξ),  x ∈ E, ξ ∈ E^{∗},

called Fenchel’s inequality. It can be stated equivalently as

ξ(x) − f̃(ξ) ⩽ f(x), x ∈ E, ξ ∈ E^{∗}.

If f is the indicator function of a set A, f = i_{A}, then f̃ = H_{A}, the supporting function of A. So the question about closed elements for the Galois correspondence studied in the example after Proposition 2.3 will be answered in the more general framework of Fenchel transforms.

We summarize the properties of the Fenchel transformation that we have found so far.

Proposition 5.1. The Fenchel transformations defined by (5.2) and (5.4) for functions on a vector space E and a subspace F of its algebraic dual form a Galois correspondence, the order of the functions being that of inclusion of their epigraphs. Thus, in terms of the usual order between functions, f ⩽ g implies f̃ ⩾ g̃, the second

transform satisfies ˜ f̃ ⩽ f, and the third transform is equal to the first, (f̃)˜ = f̃. All Fenchel transforms are convex, lower semicontinuous with respect to the topology σ(E, F) or σ(F, E), and take the value −∞ only when they are identically −∞.

Proof. Only the last statement does not follow from general properties of Galois correspondences; cf. Proposition 2.1. A supremum of a family of convex functions is convex, in particular so is f̃. Also the supremum of a family of lower semicontinuous functions is lower semicontinuous. The last property is obvious: if a Fenchel transform f̃ assumes the value −∞ for a particular ξ, then f must be equal to +∞ identically, and so f̃ is equal to −∞ identically.

For examples of Fenchel transforms, see for instance Kiselman [1991a or b].

Proposition 5.2. For any function f: E → [−∞, +∞] on a finite-dimensional vector space the following three conditions are equivalent:

1. f is lower semicontinuous, i.e., lim inf_{y→x} f(y) = f(x) for all x ∈ E;

2. epi f is closed in E × R;

3. For every real number a the sublevel set {x ∈ E; f(x) ⩽ a} is closed in E. We leave the proof as an exercise.

Theorem 5.3. Let a function f: E → [−∞, +∞] on a finite-dimensional vector space E be given. Then the following properties are equivalent: (A) f is a Fenchel transform; (B) f is equal to the supremum of all its affine minorants; (C) f is equal to the supremum of some family of affine functions; (D) f is convex, lower semicontinuous, and takes the value −∞ only if it is identically equal to −∞.

Proof. From Proposition 5.1 and the discussion preceding it is clear that (A), (B), and (C) are all equivalent, and that they imply (D). We need to prove that (D) implies (B), say.

Let us first note that (B) certainly holds if f is either +∞ or −∞. We may therefore suppose that epi f is nonempty and not equal to the whole space.

We shall prove, assuming that (D) holds, that for any point x_{0} the supremum of all affine minorants of f is equal to f(x_{0}); equivalently, that for any point (x_{0}, t_{0}) not in the epigraph of f there is an affine function which takes a value greater than t_{0} at x_{0}. Since (x_{0}, t_{0}) ∉ epi f there is a supporting half-space containing epi f and not containing (x_{0}, t_{0}). Such a half-space in E × R is defined by an inequality

ξ(x) + bt ⩾ c

for some ξ ∈ E′ and some real numbers b, c. Since the half-space is supporting, we know that there is some point (x_{1}, t_{1}) ∈ epi f which satisfies ξ(x_{1})+bt_{1} = c. If b < 0, the half-space is the epigraph of an affine function, and since its value at x_{0} is larger than t_{0}, we are done. If b > 0, the half-space is the hypograph of an affine function, and it can contain epi f only if the latter is empty, i.e., f = +∞ identically, a case we already considered. Thus only the case b = 0, that of a vertical half-space, remains to be considered. A vertical hyperplane is not the graph of an affine function, and we need to prove that these vertical hyperplanes, although they can occur, do not influence the intersection of all supporting half-spaces.

Thus we have a point (x_{0}, t_{0}) not belonging to epi f and a vertical half-space {(x, t) ∈ E × R; ξ(x) ⩾ c} which contains epi f and is such that the closest point (x_{1}, t_{1}) in epi f lies in the boundary of the half-space. Then this point must have the same t-coordinate as (x_{0}, t_{0}), so t_{1} = t_{0}. Since (x_{1}, t_{1}) belongs to epi f, the value t_{2} of f at x_{1} must satisfy −∞ < t_{2} = f(x_{1}) ⩽ t_{1} = t_{0}. It is now clear that the closest point in epi f to the point (x_{0}, t_{2}) is (x_{1}, t_{2}) and that the hyperplane obtained from our construction is the same, ξ(x) ⩾ c = ξ(x_{1}). But for points (x_{0}, t_{3}) with t_{3} < t_{2} the supporting hyperplane cannot be vertical. Even more interesting is the fact that the supporting hyperplane has a large slope when t_{3} is close to t_{2}. Consider the largest open ball which does not meet epi f and has its center at (x_{0}, t_{3}). Its closure contains a single point of epi f; denote that point by (x_{2}, t_{4}) and let R be the radius of the ball. We must have t_{4} > t_{3}. The tangent plane to the ball at (x_{2}, t_{4}) intersects the line x = x_{0} at a point (x_{0}, t_{3} + T), where T = R^{2}/(t_{4} − t_{3}). Since (x_{1}, t_{3}) does not belong to epi f we must have R > ∥x_{1} − x_{0}∥ and t_{4} > t_{3}. On the other hand

R = \sqrt{∥x_{2} − x_{0}∥^{2} + (t_{4} − t_{3})^{2}} ⩽ \sqrt{∥x_{1} − x_{0}∥^{2} + (t_{2} − t_{3})^{2}},

since (x_{2}, t_{4}) is the point in epi f closest to (x_{0}, t_{3}) and (x_{1}, t_{2}) is a point in epi f. Now ∥x_{2} − x_{0}∥ > ∥x_{1} − x_{0}∥, so

(t_{4} − t_{3})^{2} ⩽ ∥x_{1} − x_{0}∥^{2} + (t_{2} − t_{3})^{2} − ∥x_{2} − x_{0}∥^{2} < (t_{2} − t_{3})^{2}.

Thus 0 < t_{4} − t_{3} < t_{2} − t_{3}. The value at x_{0} of the affine function defined by the tangent plane is t_{3} + T and tends to plus infinity as t_{3} ↗ t_{2} since

T = \frac{R^{2}}{t_{4} − t_{3}} > \frac{∥x_{1} − x_{0}∥^{2}}{t_{2} − t_{3}} ;

in particular t_{3} + T is larger than t_{0} for some t_{3} close to t_{2}. This proves that the intersection of all supporting half-spaces is not affected if we remove the vertical half-spaces and completes the proof of the theorem.

We now know that the closed elements for the Galois correspondence defined in Proposition 5.1 consists of the functions satisfying condition (D) of Theorem 5.3. An indicator function i_{A} is closed if and only if the set A is closed and convex. Under the Fenchel transformation these functions are in bijective correspondence with the supporting functions of closed convex sets.

The supporting function mapping A ↦ H_{A} embeds the semigroup of all nonempty compact convex subsets of a vector space E into the group of real-valued functions on E′. Thus for instance the equation A + X = B, which for nonempty compact convex sets is equivalent to H_{A} + H_{X} = H_{B}, can sometimes be solved by a set X, viz. when H_{X} = H_{B} − H_{A} is convex. For applications of the supporting function in image analysis, see Ghosh & Kumar [1998].

Next we shall study the relation between infimal convolution and the Fenchel transformation. The first result is very easy.

Proposition 5.4. For all functions f, g: R^{n} → [−∞, +∞] we have

(5.6)  (f ⊓ ⊔ g) = f̃+ · g̃.

In particular, if we take f = i_{X}, g = i_{Y} with arbitrary sets X and Y,

(5.7)  H_{X+Y} = (i_{X} ⊓ ⊔ i_{Y}) = H_{X} + · H_{Y} .

Proof. An easy calculation thanks to the rule (3.3).

We note that we have lower addition in (5.6). We know that f̃+ · g̃ is convex. However, it turns out that f̃+ · g̃ = f̃+ · g̃ except when f̃+ · g̃ is the constant −∞. Thus

also f̃+ · g̃ is convex. In (5.7) we can write H_{X} +H_{Y} without risk of misunderstanding if X and Y are nonempty.

Corollary 5.5. If ˜ f̃ = f and ˜ g̃ = g, then

(5.8)  (f + · g) = (f̃ ⊓ ⊔ g̃)˜ .

In particular, taking f = i_{X}, g = i_{Y} with X and Y closed and convex we have

(5.9)  H_{X∩Y} = (i_{X} + i_{Y}) = (H_{X} ⊓ ⊔ H_{Y})˜ = (min(H_{X}, H_{Y}))˜ ,

and, taking f = H_{X}, g = H_{Y} with X and Y closed and convex,

(5.10)  (H_{X} + · H_{Y}) = (i_{X} ⊓ ⊔ i_{Y})˜ = (i_{X+Y})˜ = i\overline{X+Y} .

Proof. The proof consists of a straightforward application of the proposition, except for the last equality in (5.10), which follows from Theorem 5.3.

More generally, we can obtain the supporting function of an intersection X = ⋂_{i∈I} X_{i} of closed convex sets X_{i}, i ∈ I, as

(5.11)  H_{X} = [ cvx ( inf_{i∈I} H_{X_{i}})]˜ = ( inf_{i∈I} H_{X_{i}})˜ .

Theorem 5.6. Suppose that ˜ f̃ = f, ˜ g̃ = g and that f̃ ⊓ ⊔ g̃ is lower semicontinuous and either nowhere minus infinity or else identically minus infinity. Then

(5.12)  (f + · g) = f̃ ⊓ ⊔ g̃.

In particular we can take the value at the origin of both sides and obtain

(5.13)  − inf_{x}(f(x) + · g(x)) = inf_{ξ}(f̃(ξ) + · g̃(−ξ)).

Proof. For the proof we only need to combine Corollary 5.5 with Theorem 5.3.

If (5.12) holds, then f̃ ⊓ ⊔ g̃ is of course lower semicontinuous, so in this respect the result cannot be improved, but it is unpleasant to have lower semicontinuity as an assumption to be verified. Formula (5.12) can be obtained from (5.13) by translation.

We remark that the assumption on f̃ ⊓ ⊔ g̃ is satisfied if the function is real-valued everywhere, for such functions are automatically continuous as shown by Theorem 3.13. However, in applications it is important to allow the value +∞.

There are important cases when (5.12) does not hold.

Example 5.7. Let f̃ = i_{X} and g̃ = i_{Y} (then X and Y are automatically closed and convex). Then f̃ ⊓ ⊔ g̃ = i_{X+Y} and Theorem 5.3 shows that (f̃ ⊓ ⊔ g̃) ˜ = i\overline{X+Y}, the indicator function of the closure of the convex set X + Y. However, X + Y is not necessarily closed. A simple example is

X = {x ∈ R^{2}; x_{2} > 0, x_{1}x_{2} ⩾ 1}, Y = {x ∈ R^{2}; x_{2} = 0},
X + Y = \{x ∈ R^{2}; x_{2} > 0\}, \overline{X + Y} = \{x ∈ R^{2}; x_{2} ⩾ 0\}.

Then f̃ ⊓ ⊔ g̃ ≠ (f̃ ⊓ ⊔ g̃) ˜ . The formula (5.12) does not hold.

Example 5.8. Define two functions f, g: R^{2} → [0, +∞] by

f(x) = \{ \begin{matrix}0, & x_{1} ⩽ −1, \\ +∞, & otherwise; \end{matrix} g(x) = \{ \begin{matrix}0, & x_{1} ⩾ 1, \\ +∞, & otherwise. \end{matrix}

Thus f = i_{X}, g = i_{Y} where X and Y are disjoint closed half-spaces. Then f + · g =

+∞ identically and f̃(ξ) = H_{X}(ξ) = −ξ_{1} when ξ_{2} = 0, ξ_{1} ⩾ 0 and +∞ otherwise, whereas g̃(ξ) = H_{Y} (ξ) = ξ_{1} when ξ_{2} = 0, ξ_{1} ⩽ 0 and +∞ otherwise. The convex function f̃ ⊓ ⊔ g̃ takes the value −∞ when ξ_{2} = 0 and +∞ otherwise. Therefore (f + · g) = (f̃ ⊓ ⊔ g̃) ˜ = −∞ identically while (f̃ ⊓ ⊔ g̃) (ξ) = +∞ when ξ_{2} ≠ 0. Thus (5.12) does not hold.

The next example is similar to the one we just considered, but in a sense worse, since now (f̃ ⊓ ⊔ g̃)(0) = 0. Example 5.9. Let

X = {x ∈ R^{2}; x_{1} > 0, x_{1}x_{2} ⩾ 1}, Y = {x ∈ R^{2}; x_{1} ⩽ 0},

and considerf = i_{X}, g = i_{Y}. Then X ∩Y = Ø, so H_{X∩Y} = −∞ identically. However,

f̃(ξ) = H_{X}(ξ) = \{ \begin{matrix}−2\sqrt{ξ_{1}ξ_{2}}, & ξ_{1} ⩽ 0, ξ_{2} ⩽ 0, \\ +∞, & otherwise, \end{matrix}

and

g̃(ξ) = H_{Y} (ξ) = \{ \begin{matrix}0, & ξ_{1} ⩾ 0, ξ_{2} = 0, \\ +∞, & otherwise, \end{matrix}

so that, by Proposition 4.10,

(f̃ ⊓ ⊔ g̃)(ξ) = (H_{X} ⊓ ⊔ H_{Y})(ξ) = cvx(min(H_{X}, H_{Y}))(ξ) = \{ \begin{matrix}−∞, & ξ_{2} < 0, \\ 0, & ξ_{2} = 0, \\ +∞, & ξ_{2} > 0. \end{matrix}

In particular we note that H_{X∩Y} (0) = −∞ while cvx(min(H_{X}, H_{Y}))(0) = 0.

Thus the double tilde in (5.8), (5.9) or (5.10) cannot be omitted in general. The formulas (5.12) and (5.13) are important in optimization, but they are quite subtle—in contrast to (5.6).

Theorem 5.10. If I is a finite or infinite index set and the A_{i} are compact convex subsets of a finite-dimensional vector space, then (5.11) can be simplified: the supporting function of the intersection A = ⋂ A_{i} is

(5.14)  H_{A} = cvx ( inf_{i} H_{A_{i}}).

In particular A is nonempty if and only if

(5.15)

∑ H_{A_{i}}(ξ^{i}) ⩾ 0 for all vectors ξ^{i}, i ∈ I, such that ξ^{i} ≠ 0

for only finitely many indices i ∈ I and ∑ ξ^{i} = 0.

Proof. Let us denote by g the right-hand side of (5.14). Clearly H_{A} ⩽ g. On the other hand, ˜ g̃ is the supporting function of some set, say ˜ g̃ = H_{Y}, and this set must be contained in every A_{i}, thus Y ⊂ A and ˜ g̃ = H_{Y} ⩽ H_{A}. So ˜ g̃ ⩽ H_{A} ⩽ g; it remains to be proved that ˜ g̃ = g.

If I is empty, both sides of (5.14) equal +∞ identically; if one of the A_{i} is empty, both sides equal −∞. So let us assume that I ≠ Ø and that A_{i} ≠ Ø for all i ∈ I. Then the H_{A_{i}} are real-valued and the right-hand side g of (5.14) never takes the value +∞, so (dom g)^{∘} is the whole space. By Theorem 3.13 g is either the constant −∞ or else a continuous real-valued function. So it satisfies ˜ g̃ = g in all cases. This proves (5.14). The last statement follows if we use the expression (3.7) for the convex hull of inf_{i} H_{A_{i}} and note that H_{A}(0) ⩾ 0 if and only if A ≠ Ø. This completes the proof.

As shown by Example 5.8, (5.14) does not necessarily hold if the A_{i} are closed half-spaces and I is finite. Moreover, Example 5.9 shows that (5.15) does not imply that the intersection is nonempty if the A_{i} are finitely many closed convex subsets. In spite of this, (5.15) does imply that the intersection is nonempty if the A_{i} are closed half-spaces, finite in number:

Theorem 5.11. Let A_{i}, i ∈ I, be finitely many closed half-spaces in a finite-dimen-sional vector space E. Then their intersection A = ⋂ A_{i} is nonempty if and only if (5.15) holds; more explicitly, if we assume that the half-spaces are defined by

(5.16)  A_{i} = {x ∈ E; η^{i}(x) ⩽ α_{i}},  i ∈ I,

for some nonzero linear forms η^{i} ∈ E′ and some real numbers α_{i}, then (5.15) takes the form

(5.17)  ∑_{i} λα_{i} ⩾ 0 for all λ_{i} ⩾ 0 with ∑_{i} λ_{i}η^{i} = 0.

Proof. The set

M = {(η^{i}, α_{i}); i ∈ I} ⊂ E′ × R

is finite and its convex hull is

cvx M = {∑ λ_{i}(η^{i}, α_{i}); λ_{i} > 0, ∑ λ_{i} = 1} .

We define M^{+} as the set of all points (ξ, τ′) with τ′ ⩾ τ for some point (ξ, τ) in M. Then cvx(M^{+}) = (cvx M)^{+}. Condition (5.15) means that a point of the form (0, τ) ∈ cvx M must satisfy τ ⩾ 0. Therefore either 0 ∉ cvx M or 0 ∈ ∂(cvx M); we also have 0 ∉ (cvx M)^{+} or 0 ∈ ∂((cvx M)^{+}). There exists a half-space

D = {(ξ, τ) ∈ E′ × R; ξ(x) + τt ⩽ 0}

which contains M^{+}. Because M^{+} contains points with large τ, t must be negative or zero—unless M is empty, but then the conclusion is true anyway. If t < 0, the inequality defining D can be written ξ(−x/t) ⩽ τ, and the fact that D contains M can be expressed as η^{i}(−x/t) ⩽ α_{i}, which means that −x/t ∈ A; we are done.

In case t = 0 we have a vertical hyperplane in E′ × R. We cannot use the technique in the proof of Theorem 5.3 to tilt the hyperplane, for we are not allowed to lower it, i.e., change the value at the origin of the linear function defining it. But on the other hand, (cvx M)^{+} is a polyhedron, which will enable us to use another method: we can tilt the hyperplane and still let it pass through the origin.

So assume that t = 0, meaning that we have a vertical half-space

D = {(ξ, τ); ξ(x) ⩽ 0}

containing M. We must then have x ≠ 0. Consider the set

J = {i ∈ I; η^{i}(x) = 0}.

If J is empty, we have η^{i}(x) < 0 for all i and we see that η^{i}(sx) ⩽ α_{i}, thus sx ∈ A, if only s is large enough. Otherwise we consider the problem with points (η^{i}, α_{i}), i ∈ J, and the subspace

F = {ξ ∈ E′; ξ(x) = 0}.

We may assume that the result is already proved in the space F, which is of smaller dimension. (For spaces of dimension 0 the result is certainly true.) So there exists a point y such that η^{i} · y ⩽ α_{i} for all i ∈ J. We now have sx + y ∈ A for s large: if i ∉ J, then η^{i}(x) < 0 and η^{i}(sx) + η^{i} · y ⩽ α_{i} for s ≫ 0; if on the other hand i ∈ J, then η^{i}(sx + y) = η^{i}(y) ⩽ α_{i} by hypothesis. Thus A is nonempty.

Finally, to see that (5.15) takes the form (5.17), it is enough to remark that the supporting functions are

H_{A_{i}}(ξ) = \{ \begin{matrix}λα_{i} if ξ = λη^{i} for some λ ⩾ 0, and \\ +∞ otherwise. \end{matrix}

Example 5.12. The conclusion of Theorem 5.11 is not necessarily true if we admit infinite intersections. Let E = R^{2} and define infinitely many half-spaces as in (5.16), taking η^{i} = (1, i) ∈ R^{2}, i ∈ Z, and α_{i} as arbitrary real numbers. Then (5.17) is satisfied regardless of the choice of the α_{i}. But A ≠ Ø if and only if

(5.18)  ∃C_{1} ∃C_{2} ∀i ∈ Z α_{i} ⩾ −C_{1} − iC_{2}.

Thus for instance the choice α_{i} = γ|i| yields a nonempty intersection if and only if γ ⩾ 0. If we take a look at the proof of Theorem 5.11 in this situation, we see that the set M is contained in a vertical half-space {(ξ, τ); ξ_{1} ⩾ 0}. This half-space can be tilted to a non-vertical half-space {(ξ, τ); τ ⩾ −C_{1}ξ_{1} − C_{2}ξ_{2}} containing M if and only if α_{i} ⩾ −C_{1} − iC_{2} for some constants C_{1}, C_{2}. (Half-spaces of the form {(ξ, τ); τ ⩾ −Cξ_{1} − C_{2}ξ_{2} − ε} with ε > 0 are not allowed here.) Thus the method of proof we have used works if and only if (5.18) holds.

Maybe we can sum up our experience concerning Theorems 5.10 and 5.11 and the related counterexamples as follows. The calculus of infimal convolution and the Fenchel transformation is highly successful and also quite easy when we consider compact convex sets. When the sets are unbounded, certain difficulties appear— but they have to be confronted! Then again polyhedra with finitely many faces are quite well-behaved even if they happen to be unbounded—but the proofs are quite different!

6. The Monge–Kantorovich problem

We shall now discuss an application of convex duality, the Monge–Kantorovich^{5} problem. It is about moving masses of earth around in the most economical way. But the masses could also be images. Kantorovich’s theory has applications in economics and image analysis.

Given two probability measures as finite sums of Dirac measures

(6.1)  μ = ∑ A_{j}δ_{a_{j}} and ν = ∑ B_{k}δ_{b_{k}},

the Kantorovich cost functional is

(6.2)  C(μ, ν) = inf_{M} ∑ m_{jk}c(a_{j}, b_{k}),

where c(a, b) denotes the cost in Euro to move one ton of earth from place a to place b, or the cost in öre to move one pixel from a to b on the screen, and where the infimum is taken over all matrices M = (m_{jk}) such that ∑_{k} m_{jk} = A_{j} (moving the mass A_{j} out from a_{j} to the various b_{k}) and ∑_{j} m_{jk} = B_{k} (moving the mass B_{k} to b_{k} from all possible a_{j}).

On a screen we may have 512 × 1024 = 2^{19} pixels, so M is a matrix with 2^{38} entries. Therefore the problem is unwieldy. Thomas Kaijser [1998] has studied it and devised algorithms to calculate the functional.

Kantorovich let the measures be arbitrary probability measures and defined the cost (or work) as an integral.

We can approximate the A_{j} and B_{k} by rational numbers, and then we can even assume that they are all equal to 1/m for some m, for the locations a_{j} and b_{k} can be repeated at will. This is the situation we shall consider here; it can be viewed as an approximation to the general problem.

So let us consider a metric space X with metric d and linear combinations of Dirac measures

(6.3)  μ = \frac{1}{m} ∑_{j=1}^{m} δ_{a_{j}},  ν = \frac{1}{m} ∑_{j=1}^{m} δ_{b_{j}},

where m ∈ N ∖ {0} and a_{j} and b_{j} are points in X, j = 1, ..., m. The points could represent pixels in an image, and the number of indices j such that a_{j} is equal to a particular point represents the brightness of the image at that point.

Let us define a distance d_{1} for such measures by putting

(6.4)  d_{1}(μ, ν) = inf_{σ} \frac{1}{m} ∑_{j=1}^{m} d(a_{j}, b_{σ(j)}),

where the infimum is taken over all permutations σ of {1, 2, ..., m}. In this case M is equal to 1/m times a permutation matrix, and the cost c(a, b) is a metric d(a, b); the

5Gaspar Monge, 1746–1818; Leonid Vital′evič Kantorovič, 1912–1986. triangle inequality will be needed. (It is probably of interest to consider other cost functionals, but then they can hardly be equal to the dual distance defined below.) Thus d_{1} measures the work needed to move μ to ν: we choose to move each a_{j} to some b_{k} and then take the most economical permutation. This is the Kantorovich distance between μ and ν. With m = 2^{19} pixels, the infimum in (6.4) is taken over (2^{19})! permutations—it is indeed unwieldy.

The dual distance d_{2} between two measures is defined by

(6.5)  d_{2}(μ, ν) = sup_{f∈Lip} |μ(f) − ν(f)|,

where Lip denotes the set of all Lipschitz functions with Lipschitz constant 1; i.e., functions f: X → R such that

|f(x) − f(y)| ⩽ d(x, y), x, y ∈ X.

Theorem 6.1 (Kantorovich [1942]). For any two measures as in (6.3) we have d_{1}(μ, ν) = d_{2}(μ, ν). This is Kantorovich’s classical theorem restricted to this special case, which, however, can be easily extended to the general case by approximating arbitrary probability measures by sums of Dirac measures. We shall present a new proof here using convex duality, more precisely Theorem 5.11. Proof. It is easy to see that d_{2} ⩽ d_{1}. To prove the inequality in the other direction we shall construct a function f = min_{j} f_{j} ∈ Lip, where

f_{j}(x) = c_{j} + d(x, b_{j}), x ∈ X, j = 1, ..., m,

for some skilfully chosen real numbers c_{j}. We want that, after some permutation of the b_{j}, f(x) = f_{j}(x) for x = a_{j}, b_{j}. If we succeed in this construction, we will have f(a_{j}) − f(b_{j}) = d(a_{j}, b_{j}) for all j and we shall obtain

d_{2}(μ, ν) ⩾ |μ(f) − ν(f)| = \frac{1}{m} ∑(f(a_{j}) − f(b_{j})) = \frac{1}{m} ∑ d(a_{j}, b_{j}) ⩾ d_{1}(μ, ν),

which will finish the proof.

Thus the question is to find levels c_{j} so that f(a_{j}) = f_{j}(a_{j}) and f(b_{j}) = f_{j}(b_{j}). Here the first equality holds if and only if f_{k}(a_{j}) ⩾ f_{j}(a_{j}) for all k, i.e., c_{k}+d(a_{j}, b_{k}) ⩾ c_{j} + d(a_{j}, b_{j}). The second holds if and only if f_{k}(b_{j}) ⩾ f_{j}(b_{j}) for all k, i.e., c_{k} + d(b_{j}, b_{k}) ⩾ c_{j}. We note that the second condition follows from the first, for if the first is satisfied, then c_{k} −c_{j} ⩾ d(a_{j}, b_{j})−d(a_{j}, b_{k}) ⩾ −d(b_{j}, b_{k}) in view of the triangle inequality. So let us forget about the second condition. We introduce the numbers θ_{jk} = d(a_{j}, b_{k}). Our task is to find numbers c_{j} such that c_{k} − c_{j} ⩾ θ_{jj} − θ_{jk} for all j, k. Such numbers can be found if and only if the θ_{jk} satisfy the condition (6.7) below.

Proposition 6.2. Given real numbers θ_{jk}, j, k = 1, ..., m, there exists numbers c_{j}, j = 1, ..., m, such that

(6.6)  c_{k} − c_{j} ⩾ θ_{jj} − θ_{jk},  j, k = 1, ..., m,

if and only if

(6.7)  ∑_{1}^{m} θ_{jj} ⩽ ∑_{1}^{m} θ_{j,σ(j)} for all permutations σ of {1, ..., m}.

Proof. It is clear that (6.7) follows from (6.6). For the converse we note that we have a purely geometric problem in R^{m} with m^{2} closed half-spaces

(6.8)  A_{jk} = {c ∈ R^{m}; c_{j} − c_{k} ⩽ θ_{jk} − θ_{jj}};

we wish to show that their intersection A is nonempty. We shall use Theorem 5.11 and the criterion (5.17); thus A is nonempty if and only if (5.17) holds. We now apply this criterion to the situation we have in the proposition. We have m^{2} half-spaces (6.8), where, in the notation of (5.16), η^{jk} = e^{(j)} − e^{(k)} and α_{jk} = θ_{jk} − θ_{jj}. We conclude that the intersection A is nonempty if and only if

(6.9) ∑_{jk} λ_{jk}(θ_{jk} − θ_{jj}) ⩾ 0 for all λ_{jk} ⩾ 0 such that ∑_{k} λ_{sk} = ∑_{j} λ_{js} for all s.

Since we can add diagonal matrices freely to (λ_{jk}) without changing either the assumption or the conclusion in (6.9), it is enough that (6.9) be satisfied for bistochastic matrices (λ_{jk}). It is even enough to require it for a special type of bistochastic matrices, viz. the permutation matrices, for the convex hull of all permutation matrices is precisely the set of bistochastic matrices. This is because the permutation matrices are the extremal points of the set of all bistochastic matrices, and a well-known theorem states that a compact convex set is the closed convex hull of its extremal points. But when (λ_{jk}) is a permutation matrix, (6.9) reduces to (6.7). This concludes the proof the proposition.

Proof of Theorem 6.1, cont’d. Is condition (6.7) satisfied in the situation of Theorem 6.1? If we put θ_{jk} = d(a_{j}, b_{k}), then (6.7) becomes

∑ d(a_{j}, b_{j}) ⩽ ∑ d(a_{j}, b_{σ(j)}).

There exists a permutation π such that

∑ d(a_{j}, b_{π(j)}) = inf_{σ} ∑ d(a_{j}, b_{σ(j)}).

We can now renumber the points b_{j} so that π becomes the identity. Then (6.7) holds, and we have proved the theorem.

7. The Brunn–Minkowski inequality

In my lectures on the Brunn–Minkowski inequality and the Prékopa–Leindler inequality I followed Ball [1997] closely. Therefore I do not include anything from these lectures here.

8. Non-convex sets

Can we extend the techniques used in convexity theory to non-convex sets? Here I shall indicate very briefly how it is possible to use the supporting function of a convex set to describe faithfully also non-convex closed sets.

Proposition 8.1. Consider the mapping p: x ↦ (x, \frac{1}{2}∥x∥^{2}) from R^{n} into R^{n+1}, where ∥ · ∥ is a Euclidean norm. The inverse image of the convex hull of the image of any set in R^{n} is equal to the set itself:

(8.1)  p^{−1}( cvx p(A)) = A,  A ⊂ R^{n}.

For closed subsets A of R^{n} we can take the closed convex hull:

(8.2)  p^{−1}(\overline{cvx p(A)}) = A,  A closed in R^{n}.

Proof. The mapping p is an embedding of R^{n} into R^{n+1}, preserves the C^{∞} structure of R^{n}, and realizes R^{n} as the paraboloid P = p(R^{n}) = \{(x, t) ∈ R^{n+1}; t = \frac{1}{2}∥x∥^{2}\}. Also P is the graph of the mapping φ: x ↦ \frac{1}{2}∥x∥^{2}, which has the property that grad φ = id_{R^{n}}.

Clearly A is contained in p^{−1}(cvx p(A)). To prove the other inclusion, observe that the tangent plane to P at a point (a, s) ∈ P is {(x, t); t − s = a · (x − a)}. The closed half-space {(x, t); t − s ⩾ a · (x − a)} contains the paraboloid. If a ∉ A, then the corresponding open half-space D = {(x, t); t − s > x · (x − a)} contains p(A) and therefore also its convex hull. Now D does not contain (a, s), so p^{−1}(D) does not contain a. This proves (8.1).

If A is closed and a ∉ A, then there is even a closed half-space of the form D_{ε} = {(x, t); t − s ⩾ a · (x − a) + ε} for some positive ε which contains p(A), hence also its closed convex hull. More precisely, if (x, t) ∈ P ∩ D_{ε}, then ∥x − a∥ ⩾ \sqrt{2ε}. Hence a ∉ p^{−1}(\overline{cvx p(A)}). This proves (8.2).

The supporting function of the paraboloid P is given by

H_{P} (ξ, τ) = \{ \begin{matrix}−\frac{1}{2τ} ∥ξ∥^{2}, & τ < 0, \\ +∞, & τ > 0 or τ = 0, ξ ≠ 0, \\ 0, & (ξ, τ) = (0, 0). \end{matrix}

The closed convex hull of the image of a set A is the intersection of all closed half-spaces containing p(A), thus

\overline{cvx p(A)} = ⋂_{ξ,τ}\{(x, t) ∈ R^{n+1}; ξ · x + τt ⩽ H_{p(A)}(ξ, τ)\}.

Hence the inverse image of \overline{cvx p(A)} is

(8.3)  p^{−1}(\overline{cvx p(A)}) = ⋂_{ξ,τ}\{x ∈ R^{n}; ξ · x + \frac{1}{2}τ∥x∥^{2} ⩽ H_{p(A)}(ξ, τ)\}.

Therefore any closed set A can be recovered from the supporting function of p(A).

We can simplify (8.3): it is not necessary to take the intersection over all (ξ, τ) ∈ R^{n} × R. With the notation

E_{τ} = ⋂_{ξ}{(x, t) ∈ R^{n} × R; ξ · x + τt ⩽ H_{p(A)}(ξ, τ)},

we can write \overline{cvx p(A)} = ⋂_{τ} E_{τ} = E_{1} ∩ E_{0} ∩ E_{−1}, for E_{τ} = E_{1} if τ is positive, E_{τ} = E_{−1} if τ is negative. I claim that E_{−1} ∩P = E_{1} ∩E_{0} ∩E_{−1} ∩P. Indeed, if (x, t) belongs to E_{−1} ∩ P, then x belongs to \overline{A}, as shown by the proof of Proposition 8.1, for there we used the half-spaces D_{ε} which have τ = −1. And if x ∈ \overline{A}, then clearly p(x) belongs to all E_{τ}. Therefore it is enough to take τ = −1 in the intersection in (8.3).

Finally we note that \overline{p(A)} = p(\overline{A}) and that \overline{cvx p(A)} = \overline{cvx (\overline{p(A)})} (cf. Proposition 2.3), so that \overline{A} = p^{−1}(\overline{cvx(p(A)}); cf. (8.2). We may now write

\overline{A} = p^{−1}(\overline{cvx p(A)}) = ⋂_{ξ}\{x ∈ R^{n}; ξ · x − \frac{1}{2}∥x∥^{2} ⩽ H_{p(A)}(ξ, −1)\}.

We also note that H_{p(A)}(a, −1) ⩽ H_{P} (a, −1) with equality precisely when a ∈ \overline{A}. We sum up the discussion as follows.

Proposition 8.2. Define for any subset A of R^{n} a function

Γ_{A}(ξ) = sup_{x∈A} (ξ · x − \frac{1}{2}∥x∥^{2}) = H_{p(A)}(ξ, −1), ξ ∈ R^{n}.

Then Γ_{A}(a) ⩽ \frac{1}{2}∥a∥^{2} everywhere, with equality if and only if a belongs to the closure of A. This idea can be used to recover the support, not just the convex hull of the support, from the Fourier transform of a distribution with compact support; see Kiselman [1981].

9. Notions of topology

9.1. Mappings Let f: X → Y be a mapping from a set X into a set Y, and denote by P (X) the power set of X, i.e., the set of all subsets of X. We associate with f a mapping f^{∗}: P (Y) → P (X) and a mapping f_{∗}: P (X) → P (Y) defined as follows. (9.1.1)

f^{∗}(B) = {x ∈ X; f(x) ∈ B} = f^{−1}(B), f_{∗}(A) = {f(x) ∈ Y; x ∈ A} = f(A).

Thus f^{∗}(B) = f^{−1}(B) is the preimage (inverse image) of B ⊂ Y and f_{∗}(A) = f(A) is the direct image (or just image) of A ⊂ X. It is however sometimes convenient to have a special notation for f_{∗}: P (X) → P (Y), so that it is not confused with f: X → Y; similarly f^{∗} is not the pointwise inverse of f.

We note that

(9.1.2)  f^{∗} ∘ f_{∗} ⩾ id_{P (X)} and f_{∗} ∘ f^{∗} ⩽ id_{P (Y)}.

Thus f^{∗}(f_{∗}(A)) ⊃ A; equality holds for all A if and only if f is injective, and f_{∗}(f^{∗}(B)) = B ∩ im f ⊂ B; equality holds for all B if and only if f is surjective.

We also note that f^{∗} is a homomorphism of Boolean algebras: it satisfies

(9.1.3) f^{∗}(B_{1} ∪ B_{2}) = f^{∗}(B_{1}) ∪ f^{∗}(B_{2}),  f^{∗}(B_{1} ∩ B_{2}) = f^{∗}(B_{1}) ∩ f^{∗}(B_{2}),

(9.1.4)  f^{∗}(B_{1} ∖ B_{2}) = f^{∗}(B_{1}) ∖ f^{∗}(B_{2}), in particular f^{∗}(∁B) = ∁f^{∗}(B).

More generally, (9.1.3) can be generalized to infinite unions and intersections. The homomorphism f^{∗} is an endomorphism if and only if f is surjective, and an epimorphism if and only if f is injective.

The mapping f_{∗} is not so well-behaved: it always satisfies

f_{∗}(A_{1} ∪ A_{2}) = f_{∗}(A_{1}) ∪ f_{∗}(A_{2}),

but only f_{∗}(A_{1} ∩ A_{2}) ⊂ f_{∗}(A_{1}) ∩ f_{∗}(A_{2}), and there is in general no inclusion relation between f_{∗}(∁A) and ∁f_{∗}(A).

9.2. Definition of topologies A topology on a set X is a collection 𝒰(X) of subsets of X, thus an element of P (P (X)), which is stable under arbitrary unions and finite intersections. The elements of 𝒰(X) are called open sets; thus any union of open sets is open and any finite intersection of open sets is open. In particular, the union and the intersection of the empty family is open, so Ø and X are always open subsets of X.

However, a topology can be given in several different ways. We define a set as closed if its complement is open. Then the family ℱ(X) of all closed sets is stable under arbitrary intersections and finite unions. We may also impose these conditions as axioms, and define a set to be open if its complement is closed. A topology can be equivalently defined using open or closed sets.

Another notion is that of neighborhood. If a topology 𝒰(X) is given, we say that a set V is a neighborhood of a point x if there exists an open set U such that x ∈ U ⊂ V. The families 𝒱(x), x ∈ X, of neighborhoods of points in X satisfy the following conditions:

(9.2.1)  If V ∈ 𝒱(x), then x ∈ V;
(9.2.2)  If V ∈ 𝒱(x) and W ⊃ V, then W ∈ 𝒱(x);
(9.2.3)  If V_{1}, V_{2} ∈ 𝒱(x), then V_{1} ∩ V_{2} ∈ 𝒱(x);
(9.2.4) If V ∈ 𝒱(x), then there exists W ∈ 𝒱(x) such that V ∈ 𝒱(y) for all y ∈ W.

These properties are easy to verify if the topology is given and the neighborhoods are defined as above. On the other hand, if we have a collection 𝒱(x) for every x ∈ X satisfying the axioms (9.2.1)–(9.2.4) and define a set U to be open if it belongs to 𝒱(x) for every x ∈ U, then we get a topology for which the neighborhoods are the given ones.

We can also define a topology using closure operators. If a topology is given, then we can define a closure operator by taking \overline{A} as the intersection of all closed sets containing A. Then this closure operator satisfies \overline{Ø} = Ø and \overline{A ∪ B} = \overline{A} ∪ \overline{B}. Conversely, if a closure operator is defined satisfying these conditions we can define a set to be closed if \overline{A} = A; we then get a topology, a topology for which the topological closure operator is the given one.

Finally, the interior A^{∘} of a set A is the largest open set contained in the set. It is related to the closure by the formula

A^{∘} = ∁ (\overline{∁A}) .

The operation A ↦ A^{∘} is shrinking, increasing (order preserving), and idempotent:

A^{∘} ⊂ A;
A_{1} ⊂ A_{2} implies A_{1}^{∘} ⊂ A_{2}^{∘}; and
(A^{∘})^{∘} = A^{∘}.

This means that it is a closure operator if we reverse the order: A ⩽ B shall mean A ⊃ B. In addition to being a closure operator, it satisfies X^{∘} = X and (A ∩ B)^{∘} = A^{∘} ∩ B^{∘}. Conversely, we may take these properties as axioms and define a set to be open if it is in the image of the operator. Then we get a topology and the operation of taking the interior of a set for this topology is equal to the original operator.

Summing up, we have five equivalent ways to define a topology: using open sets, closed sets, neighborhoods, taking the topological closure, and taking the interior.

If we have two topologies 𝒰_{1}(X) and 𝒰_{2}(X) on the same set X we say that the first is weaker or coarser than the second, and that the second is finer or stronger than the first, if 𝒰_{1}(X) ⊂ 𝒰_{2}(X). Expressed in terms of closure operators, this means that c_{2} ⩽ c_{1} if c_{j} denotes the closure operator associated with 𝒰_{j}(X), j = 1, 2. The weakest topology is the chaotic topology {Ø, X} and the strongest is the discrete topology P (X). The closure of a nonempty set in the chaotic topology is always the whole space, wheras the closure of a set in the discrete topology is the set itself.

A two-point space can have four topologies: in addition to the two just mentioned, they are {Ø, {x}, {x, y}} and {Ø, {y}, {x, y}}. The two latter are called Sierpiński^{6} topologies. How many topologies are there on a three-point space?

9.3. Transport of topologies If f: X → Y is a mapping from a set X into a topological space Y we can transport the topology on Y to X by defining a subset of X to be open if and only if it is of the form f^{∗}(U) for some open subset U of Y. Because of (9.1.3) and the corresponding formula for infinite unions it is clear that the family of all sets

(f^{∗})_{∗}(𝒰(Y)) = {f^{∗}(U); U ∈ 𝒰(Y)}

is a topology. Here we have used the notation introduced in (9.1.1) at the next higher level: f^{∗}: P (Y) → P (X), (f^{∗})_{∗}: P (P (Y)) → P (P (X)). For brevity we shall denote (f^{∗})_{∗}(𝒰(Y)) by f^{←}(𝒰(Y)), the pull-back of 𝒰(Y).

If d: Y → Y is a closure operator in Y, then d^{←} = f^{∗}∘d∘f_{∗} is a closure operator in X, and if d satisfies the topological axioms d(Ø) = Ø and d(B_{1}∪B_{2}) = d(B_{1})∪d(B_{2}), then d^{←} does the same. Thus we can transport topological closure operators from Y

6Wacław Sierpiński, 1882–1969. to X. One can verify that the transported open sets correspond to the transported closure operator.

A particularly common case is when X is a subset of Y and f is the inclusion mapping. Then we say that the topology f^{←}(𝒰(Y)) defined on X is the induced topology. We see that U is open in X if and only if U = V ∩ Y for some open set in Y; we also see that the closure operator d^{←} in X is defined as d^{←}(A) = d(A) ∩ X.

If X is a topological space and f: X → Y a mapping of X into a set Y, we can of course consider the family {f_{∗}(A); A ∈ 𝒰(X)}. However, since f_{∗} is not so well-behaved, it is usually not a topology on Y. Instead we use again f^{∗} and declare a subset B of Y to be open if f^{∗}(B) is open in X. And we can verify that this is indeed a topology on Y; we shall denote it by

f_{→}(𝒰(X)) = (f^{∗})^{∗}(𝒰(X)) = {B ∈ P (Y); f^{∗}(B) ∈ 𝒰(X)},

the push-forward of 𝒰(X).

A common instance of this definition is when Y is a quotient set of X, i.e., when we have an equivalence relation ∼ in X and let Y = X/∼ be the set of all equivalence classes in X with respect to the relation. The mapping f associates to each element in X its equivalence class in Y. Then a subset B of Y is open in Y with respect to the topology we have pushed forward from X if and only if the union of all equivalence classes in B is open in X. The topology obtained in this way on X/∼ is called the quotient topology.

If f: X → Y is injective, and if we have a topology on X, push it forward to Y and then pull it back to X, the new topology agrees with the original one: f^{←}(f_{→}(𝒰(X))) = 𝒰(X). Similarly, if f is surjective and we start with a topology on Y, pull it back to X and then push it forward to Y, we obtain the original topology; f_{→}(f^{←}(𝒰(Y))) = 𝒰(Y). (This works so well because we did not use f_{∗} but f^{∗} in the definition.)

However, if we have a closure operator c in X, we cannot define a closure operator in Y by something like c_{→} = f_{∗} ∘ c ∘ f^{∗}. In general c_{→} will not be expanding, nor idempotent. (Construct examples!) How shall we define the closure operator connected with the topology f_{→}(𝒰(X)) on Y?

9.4. Continuous mappings Let f: X → Y be a mapping of a topological space X into a topological space Y and x a point in X. We say that f is continuous at x if f^{∗}(V) is a neighborhood of x for every neighborhood V of f(x). It is called continuous if it is continuous at every point in X. We now translate this well-known notion into the language of open sets, closed sets, and closure operators. Then we can prove that f is continuous if and only if f^{∗}(U) ∈ 𝒰(X) for every U ∈ 𝒰(Y); in other words if and only if the topology f^{←}(𝒰(Y)) is weaker than the topology 𝒰(X).

9.5. Connectedness The family of all open and closed sets of a topological space X (sometimes called the clopen sets) forms a Boolean algebra. This algebra must contain the two sets Ø, X, for they are always both open and closed. (If X is empty there is only one such set, of course.) A topological space is said to be connected if it is nonempty and the only sets which are both open and closed are the empty set and the whole space.

A subset of a topological space is called connected if it is connected as a topological space with the induced topology.^{7} A connectivity component of a topological space is a connected subset which is maximal with respect to inclusion.

A connected subset which is both open and closed is a component. It is easy to prove that the closure of a connected subset is connected. Therefore all components are closed. They need not be open.

Proposition 9.5.1. Let f: X → Y be a continuous mapping of a topological space X into a topological space Y. If X is connected, then so is f_{∗}(X) = im f.

Proof. Let B be a clopen subset of im f. Then f^{∗}(B) is clopen in X. Hence f^{∗}(B) is either empty or equal to X. Therefore f_{∗}(f^{∗}(B)) = B ∩ im f = B is either empty or equal to im f. This means that im f is connected.

Corollary 9.5.2. Let f: X → Y be a mapping of a topological space X into a set Y. Equip Y with the strongest topology such that f is continuous. Suppose that X is connected. Then im f is connected, and the points in Y ∖ im f are isolated. In particular, any quotient space of a connected topological space is connected.

Proof. For any point y ∈ Y not in the image of f, the inverse image f^{−1}(y) = f^{∗}({y}) is empty, thus both open and closed. This means that Y ∖ im f has the discrete topology and the connectivity components are just the singleton sets.

In particular we shall use Corollary 9.5.2 with X = R and Y = Z to define connected topologies on the digital line Z. Let f: R → Z be a surjective mapping. Then Z equipped with the strongest topology such that f is continuous is a connected topological space. Thus we consider Z as a quotient space of R, not as a subspace. It is not unnatural to restrict attention to increasing mappings f: R → Z. For every n ∈ Z we then have two numbers a_{n} < b_{n} such that

]a_{n}, b_{n}[ ⊂ f^{∗}(n) ⊂ [a_{n}, b_{n}].

We can normalize the situation to a_{n} = n, b_{n} = n + 1; this does not change the topology on Z. Then f(x) = ⌊x⌋ for all x ∈ R ∖ Z, and f(n) = n or f(n) = n − 1, n ∈ Z. The topology is therefore determined if we know for which n we have f(n) = n − 1. For every subset A of Z we get a topology on Z by declaring that f(n) = n − 1 for a ∈ A and that, for all other real numbers x, we have f(x) = ⌊x⌋.

Another normalization is to take a_{n} = n − \frac{1}{2}, b_{n} = n + \frac{1}{2}. This can be explained as follows. It is natural to think of Z as an approximation of the real line R and to consider mappings f: R → Z expressing this idea. We may define f(x) to be the integer closest to x; this is well-defined unless x is a half-integer. So when x = n+ \frac{1}{2} we have a choice for each n: shall we define f(n+ \frac{1}{2}) = n or f(n+ \frac{1}{2}) = n+1? If we choose the first alternative for every n, thus putting f^{∗}(n) = ]n − \frac{1}{2}, n + \frac{1}{2}], the topology defined in Corollary 9.5.2 is called the right topology on Z; if we choose the second, we obtain the left topology on Z; cf. Bourbaki [1961:I:§1: Exerc. 2]. Another choice is

7According to Bourbaki [1961:I:§11:1] the empty space is connected. Here I follow instead the advice of Adrien Douady (personal communication, June 26, 2000). In these notes it will not matter whether the empty set is said to be connected or not. to always choose an even integer as the best approximant of a half-integer. Then the closed interval [−\frac{1}{2}, \frac{1}{2}] is mapped to 0, so \{0\} is closed, whereas the inverse image of 1 is the open interval ]\frac{1}{2}, \frac{3}{2}[, so that \{1\} is open. This topology was introduced by E. D. Halimskiĭ (Efim Khalimsky), and we shall call it the Khalimsky topology; Z with this topology is called the Khalimsky line. The Khalimsky line is connected, but the complement of any point is disconnected. Among all the topologies defined by increasing surjections f: R → Z only two have this property: the one just defined and the one obtained by translating everything by one step.

9.6. Separation axioms and adjacency The closure of a subset A of a topological space X will be denoted by \overline{A}. The intersection of all neighborhoods of a point x will be denoted by N(x). We note that x ∈ \overline{\{y\}} if and only if y ∈ N(x). The relation x ∈ \overline{\{y\}} defines a preorder in X, i.e., a relation satisfying (2.1) and (2.3) but not necessarily (2.2). We shall denote it by x ≼ y; thus x ≼ y if and only if x ∈ \overline{\{y\}}. It was introduced by Aleksandrov [1937:503]. We shall call it the specialization preorder; cf. Kong et al. [1991:905].

A Kolmogorov space (Bourbaki [1961:I:§1: Exerc. 2]), also called a T_{0}-space, is a topological space such that x ∈ N(y) and y ∈ N(x) only if x = y, thus precisely when the specialization preorder is an order (satisfies (2.2)). Conversely, every ordered set can be made into a T_{0}-space by defining the smallest neighborhood of a point x to be N(x) = {y ∈ X; x ≼ y}. It is quite reasonable to impose this axiom; if x belongs to the closure of {y} and vice versa, then x and y are indistinguishable from the point of view of topology. (We should therefore identify them and consider a quotient space.)

The separation axiom T_{1} states that N(x) = {x}. It is too strong to be of interest for the spaces considered here. Also the specialization preorder becomes uninteresting: we have x ≼ y if and only if x = y.

Two points x and y in a topological space Y are said to be adjacent if x ≠ y and {x, y} is connected. We note that {x, y} is connected if and only if either x ∈ N(y) or y ∈ N(x). We shall say that two points x, z are second adjacent if x ≠ z; x and z are not adjacent; and there exists a third point y ∈ Y such that x and y are adjacent and y and z are adjacent.

10. Smallest neighborhood spaces

In a topological space the union of any family of open sets is open. It may happen that also the intersection of any family of open sets is open. Equivalently, every point in the space possesses a smallest neighborhood. A space with this property we shall call here a smallest neighborhood space. Another suitable name would be a P. S. Aleksandrov space, in honor of P. S. Aleksandrov,^{8} who introduced them in [1935, 1937]. It is equivalent to require that the union of an arbitrary family of closed sets is closed.

The intersection N(x) of all neighborhoods of a point x is open for all x if and only if the space is a smallest neighborhood space.

Aleksandrov [1935, 1937] introduced the term espace discret, diskreter Raum (discrete space) for a topological space such that the intersection of any family of

8Pavel Sergeevič Aleksandrov, 1896–1982; not to be confused with Aleksandr Danilovič Aleksandrov, b. 1912. open sets is open. The intersection of all closed sets containing a set M he called its Hülle (hull), and denoted it by \overline{M} or AM. The intersection of all open sets containing a set M he called its Stern (star) and denoted it by OM. He noted that the star of a set is a closure operation, and therefore defines a topology, which he called réciproque [1935] or dual [1937]. The closed set of a smallest neighborhood space satisfies the axioms of the open sets of a topology, so there is a complete symmetry between the two topologies in such a space.

Alexandrov’s choice of terms seems fortunate, but nowadays it is not possible to use the term discrete space in Aleksandrov’s sense, since the discrete topology in modern usage refers only to the topology where every set is open, the strongest of all topologies. This is why I propose to call a discrete space in Aleksandrov’s sense a smallest neighborhood space or a P. S. Aleksandrov space.

The closed points, i.e., the points x such that \overline{\{x\}} = \{x\}, Aleksandrov called Eckpunkte (vertices), and the open points, i.e., the points x such that the singleton {x} is open, he called Grundpunkte (base points).

We can define a topology on the digital line Z by declaring all odd points to be open, thus N(2k +1) = {2k +1}, and all even points to have a smallest neighborhood N(2k) = {2k − 1, 2k, 2k + 1}. It follows that the even points are closed, for the complement of an even point 2k is the union of all N(x) with x ≠ 2k, thus an open set. This is the Khalimsky topology already defined in Section 9.5. Thus in the Khalimsky topology the even points are Eckpunkte and the odd points are Grundpunkte in Aleksandrov’s terminology. In the specialization order, the base points are higher than the vertices...

A Khalimsky interval is an interval [a, b]∩Z equipped with the topology induced by the Khalimsky topology on Z. A Khalimsky circle is a quotient space Z_{m} = Z/mZ of the Khalimsky line for some even integer m ⩾ 4. (If m is odd, the quotient space receives the chaotic topology, which is not interesting.)

The Khalimsky plane is the Cartesian product of two Khalimsky lines, and more generally, Khalimsky n-space is the Cartesian product of n copies of Z. Equivalently, we can define Khalimsky n-space on Z^{n} by declaring {x ∈ Z^{n}; ∥x − c∥_{∞} ⩽ 1} to be open for any point c ∈ (2Z)^{n} and then taking all intersections of such sets as open sets, then all unions of such intersections.

There are, however, other topologies in Z^{2} which are of interest: we may declare {x ∈ Z^{2}; ∥x − c∥_{1} ⩽ 1} to be open for any c such that ∑ c_{j} ∈ 2Z as well as all intersections of such sets.^{9} The Khalimsky topology and the topology just defined are not comparable: none is stronger than the other. However, they are related, for if we turn the Khalimsky plane 45^{∘} and delete all points which are not open or closed, we obtain the new topology; see the proof of Theorem 11.3.1.

11. Digital Jordan curve theorems

The classical Jordan curve theorem says that the complement of a Jordan curve in the Euclidean plane R^{2} consists of exactly two connectivity components. Efim

9I found this topology in response to a question asked by Timur Sadykov on February 1, 2000. However, I found out later that it was defined already by Wyse [1970]; see Section 11.3.

Khalimsky’s digital Jordan curve theorem states the same thing for the digital plane Z^{2}. Of course we must use a suitable definition of the concept of digital Jordan curve, as well as a suitable topology on Z^{2}. In this case Z^{2} is given the Cartesian product topology of two copies of the digital line Z equipped with the Khalimsky topology.

A proof of Khalimsky’s theorem was published in 1990 by Khalimsky, Kopperman and Meyer [1990]. They refer to earlier proofs by Khalimsky (E. D. Halimskiĭ) [1970, 1977]. We shall present a new, short proof here.

The idea of the proof is simple. For the smallest Jordan curves (having four or eight points) the conclusion of the theorem can be proved by inspection. Given any other Jordan curve J, we construct a Jordan curve J′ which has shorter Euclidean length and is such that its complement has as many components as the complement of J. Since the possible Euclidean lengths form a discrete set, this procedure will lead to one of the smallest Jordan curves, for which the theorem is already established. The construction of J′ can intuitively be described as follows: attack J where its curvature is maximal and shorten it there; it cannot offer resistance from within.

We then consider a topology on Z^{2} which is not a product topology. In contrast to the Khalimsky topology it has the property that every point is either open or closed. We prove that the Jordan curve theorem holds for this topology for a restricted class of Jordan curves.

11.1. Khalimsky Jordan curves Khalimsky, Kopperman and Meyer [1990: 3.1] used the following definitions of path and arc in the Khalimsky plane. We just extend them here to any topological space. We modify slightly their definition of a Jordan curve [1990: 5.1]. A Jordan curve in the Euclidean plane R^{2} is a homeomorphic image of the circle R/Z, and similarly a Khalimsky Jordan curve is a homeomorphic image of a Khalimsky circle.

Definition 11.1.1. Let Y be any topological space. A Khalimsky path in Y is a continuous image of a Khalimsky interval. A Khalimsky arc is a homeomorphic image of a Khalimsky interval. A Khalimsky Jordan curve in Y is a homeomorphic image of a Khalimsky circle.

Sometimes Khalimsky Jordan curves are too narrow. We impose a condition on them to make their interior fatter:

Definition 11.1.2. Let J be a Khalimsky Jordan curve in a topological space Y. We shall say that J is strict if every point in J is second adjacent to exactly two points in J.

We note that if x, z ∈ J are second adjacent, then the intermediary y required by the definition need not belong to J. Thus the concept of strict Jordan curve is not intrinsic.

A three-set {x, y, z} such that all three points are adjacent to each other can be a Khalimsky path but never a Khalimsky arc. This follows from the fact that in a Khalimsky interval [a, b], the endpoints a and b are not adjacent unless b = a + 1. Let us say that a three-set {x, y, z} in a topological space is a forbidden triangle if all points are adjacent to each other. The absence of forbidden triangles is therefore a necessary condition for Khalimsky arcs and consequently for Khalimsky Jordan curves, and it is often easy to check.

Different topologies may induce the same adjacency structure. However, when the adjacency structure is that of a Khalimsky circle, the topology of the space must also be that of a Khalimsky circle. More precisely we have the following result.

Theorem 11.1.3. Given a subset J of a topological space Y, the following conditions are equivalent. (A) J is a Khalimsky Jordan curve. (B) J has at least four points, and for every a ∈ J, J ∖ {a} is homeomorphic to a

Khalimsky interval. (C) J is finite, connected, with cardinality at least 4, and each of its elements has

exactly two adjacent points. (D) J has the adjacency structure of a Khalimsky circle, i.e., J = {x_{1}, x_{2}, ..., x_{m}}

for some even integer m ⩾ 4 and for each j = 1, ..., m, x_{j−1} and x_{j+1} and no other points are adjacent to x_{j}. (Here we count indices modulo m.)

Proof. If (A) holds, then for every a ∈ J, J ∖ {a} is homeomorphic to a Khalimsky circle minus one point, thus to a Khalimsky interval. Conversely, suppose that (B) holds and consider J ∖ {a} and J ∖ {b} for two points a, b ∈ J which are not adjacent. Then we have homeomorphisms of J ∖ {a} and J ∖ {b} into a Khalimsky circle Z_{m}. We can modify them by rotating the circle so that the two mappings agree on J ∖ {a, b}. Then they define a local homeomorphism of J onto Z_{m}, thus a homeomorphism; we have proved (A).

It is clear that (A) implies (C) and (D).

Suppose that (C) holds. Then call an arbitrary point x_{1} and one of its adjacent points x_{2} and then go on, always choosing x_{j+1} after x_{j} so that x_{j+1} is adjacent to x_{j} but not equal to any of the already chosen x_{1}, ..., x_{j−1}. After a while we must arrive at a situation where there are no new points left, i.e., we arrive at x_{m} and the two points adjacent to x_{m} are x_{m−1} and a point which has already been chosen, say x_{k}. A priori k may be any of 1, 2, ..., m − 2, but in fact the only possibility is k = 1—any other choice would mean that x_{k} had three adjacent points contrary to the assumption. It remains to be seen that m is even. That x_{j} and x_{j+1} are adjacent means that we have either x_{j} ∈ N(x_{j+1}) or x_{j+1} ∈ N(x_{j}). If x_{j} ∈ N(x_{j+1}), then we cannot have x_{j+1} ∈ N(x_{j+2}), for that would imply that x_{j} belonged to N(x_{j+2}), so that x_{j+2} would have three adjacent elements, viz. x_{j}, x_{j+1} and x_{j+3}. So the statement x_{j} ∈ N(x_{j+1}) holds only for j of a certain parity. Since this is true modulo m, that number must be even. Thus we have proved (D). Conversely, (D) obviously implies (C) since (D) is just a more detailed version of (C).

It remains to be seen that (D) implies (A). First of all it is clear that, assuming (D), N(x) can never have more than three elements—a fourth element would mean that x had at least three adjacent points. So N(x_{j}) ⊂ {x_{j−1}, x_{j}, x_{j+1}}. Considering the three points x_{j−1}, x_{j}, x_{j+1}, we note that either x_{j−1} ∈ N(x_{j}) or x_{j} ∈ N(x_{j−1}), and that x_{j} ∈ N(x_{j+1}) or x_{j+1} ∈ N(x_{j}). However, these alternatives cannot be chosen at will, for as we have seen in the previous paragraph x_{j−1} ∈ N(x_{j}) implies x_{j} ∉ N(x_{j+1}). Consider now the case x_{j−1} ∈ N(x_{j}). Then x_{j+1} ∈ N(x_{j}), so that N(x_{j}) ⊃ {x_{j−1}, x_{j}, x_{j+1}}. On the other hand we know already that N(x_{j}) has at most three elements; we conclude that N(x_{j}) = {x_{j−1}, x_{j}, x_{j+1}}. By the same argument, N(x_{j+2}) = {x_{j+1}, x_{j+2}, x_{j+3}}. Therefore N(x_{j+1}) = {x_{j+1}}, and we have proved that Y is a Khalimsky circle where points with indices of the same parity as j have three-neighborhoods and points with indices of the other parity are open. The other possibility, viz. that x_{j} ∈ N(x_{j−1}), can be reduced to the former by just shifting the indices one step.

It follows from property (C) that two Khalimsky Jordan curves can never be contained in each other. More precisely, if J and K are Khalimsky Jordan curves and J ⊂ K, then J = K.

A point on a Khalimsky Jordan curve J consisting of at least six points has at least two second adjacent points; with the order introduced in property (D), x_{j−2} and x_{j+2} are second adjacent to x_{j} and x_{j−2} ≠ x_{j+2} when m > 4. Then x_{j±1} serve as intermediaries, but there may also exist other intermediaries. When a Jordan curve is not strict and m > 4, then some point, say x_{j}, has at least one second adjacent point in addition to x_{j−2} and x_{j+2}, say x_{k}. Then an intermediary b such that x_{j} and b are adjacent and b and x_{k} are adjacent cannot belong to J.

Suppose now that Y is a metric space with metric d. Since every Khalimsky arc Γ is homeomorphic either to [0, m−1]∩Z or to [1, m]∩Z for some m, it can be indexed as {x_{1}, ..., x_{m}}, where the indices are uniquely determined except for inversion. We may define its length as

length(Γ) = ∑_{1}^{m−1} d(x_{j+1}, x_{j}).

Similarly, a Khalimsky Jordan curve can be indexed as {x_{1}, ..., x_{m}}, where the indices are uniquely determined up to inversion and circular permutations, and its length can be defined as

length(J) = ∑_{1}^{m} d(x_{j+1}, x_{j}),

where we count the indices modulo m.

We shall use the following norms in R^{2} to measure distances in Z^{2}:

∥x∥_{p} = ∥(x_{1}, x_{2})∥_{p} = \{ \begin{matrix}(|x_{1}|^{p} + |x_{2}|^{p})^{1/p}, & x ∈ R^{2}, 1 ⩽ p < +∞; \\ max (|x_{1}|, |x_{2}|), & x ∈ R^{2}, p = ∞. \end{matrix}

11.2. Khalimsky’s digital Jordan curve theorem The Khalimsky topology of the digital plane is the Cartesian product topology of two copies of the Khalimsky line Z. A point x = (x_{1}, x_{2}) in the product Z^{2} = Z × Z is closed if and only if both x_{1} and x_{2} are closed, thus if and only if both x_{1} and x_{2} are even; similarly x is open if and only if both coordinates are odd. These points are called pure; the other points, which are neither open nor closed, are called mixed.

Perhaps the quickest way to describe Khalimsky’s topology τ_{∞} on Z^{2} is this: We first declare the nine-set

(11.2.1) U_{∞} = {x ∈ Z^{2}; ∥x∥_{∞} ⩽ 1} = {(0, 0), ±(1, 0), ±(1, 1), ±(0, 1), ±(−1, 1)}

to be open, as well as all translates U_{∞} + c with c_{1}, c_{2} ∈ 2Z. Then all intersections of such translates are open, as well as all unions of the sets so obtained. As a consequence, {(1, −1), (1, 0), (1, 1)}, the intersection of U_{∞} and U_{∞} + (2, 0), and {(1, 1)}, the intersection of U_{∞} and U_{∞} + (2, 2), are open sets, and {(0, 0)} is a closed set. The sets {(1, 0)} and {(0, 1)} are neither open nor closed.

Theorem 11.2.1. Given a subset J of Z^{2} equipped with the Khalimsky topology, the conditions A, B, C and D of Theorem 11.1.3 are all equivalent to the following. (E) J = {x^{(1)}, x^{(2)}, ..., x^{(m)}} for some even integer m ⩾ 4 and for all j, x^{(j−1)} and x^{(j+1)} and no other points are adjacent to x^{(j)}; moreover each path consisting of three consecutive points {x^{(j−1)}, x^{(j)}, x^{(j+1)}} turns at x^{(j)} by 45^{∘} or 90^{∘} or not at all if x^{(j)} is a pure point, and goes straight ahead if x^{(j)} is mixed. Here we use the informal expression “turn by 45^{∘}” etc. with reference to angles in the Euclidean plane of which we consider the Khalimsky plane to be a subset (not a subspace). Proof. If (D) holds, we see that J cannot turn at a mixed point and cannot turn 135^{∘} at a pure point—otherwise we would have a forbidden triangle. So (D) implies (E). Conversely, (E) is just a more precise version of (D), so (E) implies (D).

In this section we shall measure the lengths of Khalimsky Jordan curves using the Euclidean metric, d(x, y) = ∥x − y∥_{2}. It is not possible to use ∥ · ∥_{1} or ∥ · ∥_{∞} in the proof of the Jordan curve theorem.

The smallest possible Jordan curve in Z^{2} is the four-set

J_{4} = {x ∈ Z^{2}; ∥x − (1, 0)∥_{1} = 1} = {(0, 0), (1, −1), (2, 0), (1, 1)}.

We add all translates of J_{4} by a vector c ∈ Z^{2} with c_{1} + c_{2} even and call these the Jordan curves of type J_{4}.

There is also a Jordan curve having eight points,

(11.2.2)  J_{8} = {x ∈ Z^{2}; ∥x∥_{∞} = 1} = U_{∞} ∖ {(0, 0)}.

This curve and all its translates by a vector c ∈ Z^{2} with c_{1} + c_{2} even we call the Jordan curves of type J_{8}.

Let us agree to call the three-set

(11.2.3)  T = {(1, 1), (0, 0), (1, −1)}

and rotations of T by 90^{∘}, 180^{∘} and 270^{∘}, as well as all translates of these sets by vectors c ∈ Z^{2} with c_{1} + c_{2} even, a removable triangle. It turns out that elimination of removable triangles is a convenient way to reduce Jordan curves, as shown by the following lemma.

Lemma 11.2.2. Let J be a Jordan curve in the Khalimsky plane and assume that J contains the three-set T defined by (11.2.3). Define

J′ = (J ∖ {(0, 0)}) ∪ {(1, 0)}.

Then either J = J_{4} or else J′ is a Jordan curve such that ∁J′ and ∁J have the same number of components, and length(J′) = length(J) − 2\sqrt{2} + 2.

Proof. Assume first that (2, 0) ∈ J, thus that J ⊃ J_{4}. Then necessarily J = J_{4}.

Next we suppose that (2, 0) ∉ J. Then J′ is a Jordan curve: J′ is a set where the new point (1, 0) plays exactly the same role topologically as the old point (0, 0) in J. Thus J′ is also homeomorphic to a Khalimsky circle.

Finally we must check that the number of components in ∁J′ is the same as that of ∁J′. Indeed, (1, 0) and (2, 0) belong to the same component of ∁J, and (0, 0) and (−1, 0) belong to the same component of ∁J′.

Theorem 11.2.3 (Khalimsky’s Jordan curve theorem). Let us equip the digital plane Z^{2} with the Khalimsky topology τ_{∞} (see (11.2.1)). Then for any Khalimsky Jordan curve J in Z^{2}, the complement ∁J = Z^{2}∖J has exactly two connectivity components.

Proof. The complement of J_{4} consists of A = {(1, 0)} and the set B of all points x with |x_{1} − 1| + |x_{2}| > 1. It is obvious that these two sets are connected. Moreover, A is closed and open in ∁J_{4}, so it is a component. Therefore, also B is closed and open in ∁J_{4} and also a component. The proof for J_{8} is similar.

Thus we know that the conclusion of the theorem holds for Jordan curves of types J_{4} and J_{8}.

Next we shall prove that if J is not of the kind already treated, then there exists a Jordan curve J′ of strictly smaller Euclidean length such that ∁J and ∁J′ have the same number of components. After a finite number of steps we must arrive at a situation where the hypothesis is no longer satisfied, which means that we have a Jordan curve of type J_{4} or J_{8}, for which the complement has two components as we already proved.

The construction of J′ is as follows. First we may assume, in view of Lemma 11.2.2, that J contains no removable triangles. Define

a_{2} = inf(x_{2}; x ∈ J).

Thus x_{2} ⩾ a_{2} for all points x ∈ J with equality for at least one x. Consider a horizontal interval

H = {(x_{1}, a_{2})} + {(0, 0), (1, 0), ..., (p, 0)}

which is maximal with respect to inclusion and consists of points in J with ordinate equal to a_{2}. The maximality implies that the two points (x_{1}−1, a_{2}) and (x_{1}+p+1, a_{2}) do not belong to J. Then we see that p must be an even number, but we cannot have p = 0, since that would imply that J contained a removable triangle, contrary to the assumption. Thus H contains at least three points. Moreover, at the endpoints of H, J must turn upwards. Indeed, since (x_{1} − 1, a_{2}) does not belong to J, exactly one of the points (x_{1} −1, a_{2} +1), (x_{1}, a_{2} +1) belongs to J; when we go left from (x_{1}, a_{2}), the curve must turn upwards by either 45^{∘} or 90^{∘}; it cannot turn downwards. Similarly, the curve turns upwards by 45^{∘} or 90^{∘} when we go right from the last point in H, viz. from (x_{1} + p, a_{2}).

We now consider the set ℐ of all maximal horizontal intervals I in J such that J turns upwards at the endpoints of I. The previous argument served just to prove that there exists such an interval. Now there exists an interval K ∈ ℐ of smallest length,

K = {y} + {(0, 0), (1, 0), ..., (q, 0)},

containing q + 1 points for some even number q ⩾ 2. We shall assume that K is of smallest length also among all intervals that can be obtained from the intervals in ℐ by rotating them 90^{∘}, 180^{∘} or 270^{∘}.

To simplify the notation we may assume (after a translation if necessary) that y = (0, 0), so that

K = {(0, 0), (1, 0), ..., (q, 0)} = [(0, 0), (q, 0)] ∩ Z^{2}.

Case 1. J turns upwards by 45^{∘} at both ends of K. This means that (−1, 1) and (q + 1, 1) both belong to J. In this case, we define

J′ = (J ∖ K) ∪ (K + (0, 1)).

This operation shortens the Euclidean length by 2\sqrt{2}−2 (but it does not shorten the l^{∞} length). We note that the interval K + (0, 1) is disjoint from J; otherwise some point in K would have three adjacent points. Moreover K + (0, 2) must be disjoint from J. Indeed, if (K + (0, 2)) ∩ J were nonempty, then either J would contain a removable triangle (contrary to our assumption) or there would exist a subinterval K′ of K + (0, 2) contained in J and such that J turns upwards at its endpoints; thus K′ ∈ ℐ. This subinterval must have fewer than q + 1 points, since (0, 2) and (q, 2) cannot belong to J—otherwise there would be a removable triangle in J. Now a shorter interval is impossible, since K is by assumption an interval in ℐ of shortest length. One checks that J′ is a Jordan curve. Indeed, the points of K +(0, 1) play the same role topologically in J′ as do the points of K in J. The number of components in the complement of J′ is the same as for J.

Case 2. J turns upwards by 90^{∘} at one end of K. Assume that (0, 1) ∈ J, the case (q, 1) ∈ J being symmetric. Then also (0, 2) ∈ J. We consider the subcases 2.1 and 2.2.

Case 2.1. (2, 2) ∉ J. We cut off a corner, i.e., we remove (0, 1), (0, 0), (1, 0), and add (1, 1). This operation shortens the Euclidean length by 4 − 2\sqrt{2} (but J′ has the same l^{1}-length as J). Since (1, 1) and (2, 2) belong to the same component of ∁J, and (0, 1), (0, 0), (1, 0), and (−1, 0) belong to the same component of ∁J′, the number of components in the respective complements are the same.

Case 2.2. (2, 2) ∈ J. We consider four subcases, 2.2.1.1, 2.2.1.2, 2.2.2.1 and 2.2.2.2.

Case 2.2.1.1. (2, 1) ∈ J, (1, 2) ∈ J. Then J contains a Jordan curve of type J_{8}, more precisely J ⊃ (1, 1) + J_{8}. So J must be equal to that curve.

Case 2.2.1.2. (2, 1) ∈ J, (1, 2) ∉ J. Remove the five points (0, 1), (0, 0), (1, 0), (2, 0), (2, 1), and add (1, 2). Thus J′ is shorter by 4. We can check that J′ has all desired properties.

Case 2.2.2.1. (2, 1) ∉ J, (1, 2) ∈ J. Turn 90^{∘} to reduce to case 2.2.1.2.

Case 2.2.2.2. (2, 1) ∉ J, (1, 2) ∉ J. This case cannot occur since q is smallest possible. To see this, define I′ as the set of all points (2, 2), (3, 2), ..., (q′, 2) ∈ J with q′ as large as possible. If J turns upwards at (q′, 2), then I′ belongs to ℐ with q′ < q, which contradicts the definition of K and q. If on the other hand J turns downwards at (q′, 2), then there exists a vertical interval consisting of three points, which becomes an interval in ℐ if we turn it 90^{∘}, thus again contradicting the definition of ℐ.

11.3. The Jordan curve theorem for another topology We define a topology τ_{1} on Z^{2} by first declaring the five-set

(11.3.1)  U_{1} = {x ∈ Z^{2}; ∥x∥_{1} ⩽ 1} = {(0, 0), ±(1, 0), ±(0, 1)}

to be open, then all translates U + c with c ∈ Z^{2}, c_{1} + c_{2} ∈ 2Z to be open, as well as all intersections of such translates. This implies that {(1, 0)} is open, and that the origin is closed. In fact, all points x ∈ Z^{2} with x_{1} +x_{2} ∈ 2Z are closed, and all points with x_{1} + x_{2} ∉ 2Z are open; there are no mixed points. This topology was described by Wyse et al. [1970] and Rosenfeld [1979: 624].

The four-set

J′_{4} = {(0, 0), (1, 0), (1, 1), (0, 1)}

is a Jordan curve for τ_{1}. However, it is not strict, for a point in J′_{4} has only one second adjacent point. Its complement is connected, so the Jordan curve theorem does not hold. The set J_{8} defined by (11.2.2) is a Khalimsky Jordan curve and its complement has exactly two components. Also J_{8} is not strict, because the point (1, 0) has three second adjacent points, viz. (0, 1), (0, −1) and (−1, 0).

Another example is the twelve-set

J_{12} = {(0, 0), (1, 0), (2, 0), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (1, 2), (0, 2), (0, 1)}.

It is a Jordan curve, not strict, and its complement has three connectivity components, viz. an infinite component and the two singleton sets {(1, 1)} and {(2, 2)}.

Theorem 11.3.1. Let Z^{2} be equipped with the topology τ_{1} just defined (see (11.3.1)). Then the complement of every strict Jordan curve has exactly two components.

Proof. For the proof we shall use the fact that Z^{2} equipped with the topology τ_{1} is homeomorphic to the subspace of all pure points in the Khalimsky plane. This fact was used also by Kong, Kopperman and Meyer [1991: 915].

Let X be the digital plane Z^{2} with the topology τ_{1}, and Y the Khalimsky plane (Z^{2} with the topology τ_{∞}). Consider the mapping φ: X → Y defined by φ(x) = (x_{1} − x_{2}, x_{1} + x_{2}). Its image φ(X) is the set of all pure points in Y, and if we equip it with the topology induced by Y it is homeomorphic to X. Moreover, the image of any Khalimsky Jordan curve J in X is a Khalimsky Jordan curve in Y. Therefore Y ∖ φ(J) has exactly two components by Theorem 11.2.3. We claim that φ(X) ∖ φ(J) has exactly two components. It is clear that this set has at least two components, so the problem is to prove that a component A of Y ∖ φ(J) gives rise to a connected set A ∩ φ(X), i.e., that the pure points in A form a connected set.

To this end, assume that a, a′ ∈ A ∩ φ(X), and consider a Khalimsky arc

{a = a^{(0)}, a^{(1)}, ..., a^{(s)} = a′}

contained in Y ∖φ(J). (Connectedness in Y is the same as arcwise connectedness; cf. Khalimsky et al. [1990: Theorem 3.2].) We shall prove that this arc can be replaced by another consisting only of pure points. So assume that a^{(j)} is a mixed point. Then its predecessor a^{(j−1)} and its successor a^{(j+1)} are both pure points. Without loss of generality, we may assume that a^{(j−1)} = (0, 0), a^{(j)} = (0, 1), and a^{(j+1)} = (0, 2).

We may then replace a^{(j)} by one of the pure points (−1, 1), (1, 1), because both of them cannot belong to φ(J). To see this, suppose that (1, 1), (−1, 1) ∈ φ(J). Then (−1, 1) would be a second adjacent point to (1, 1), and this point has, by hypothesis, exactly two second adjacent points in φ(J) (considering everything in the space φ(X)). However, none of them can be equal to (−1, 1), for the only possible intermediaries would then be (0, 0) and (0, 2), none of which belongs to φ(J). (In a strict Jordan curve, one of the possible intermediaries to a second adjacent point must belong to the curve.) This contradiction shows that not both of (1, 1) and (−1, 1) can belong to φ(J). Thus we may define b = (−1, 1) or b = (1, 1) so that b ∉ φ(J) and observe that

{a^{(0)}, ..., a^{(j−1)}, b, a^{(j+1)}, ..., a^{(s)}}

is a Khalimsky arc with a mixed point replaced by a pure point. After finitely many such replacements we obtain an arc connecting a and a′ and consisting only of pure points. This shows that φ(X) ∖ φ(J) has at most as many components as Y ∖ φ(J); therefore exactly two components, and then the same is true of X ∖ J.

References

Alexandroff, Paul [Aleksandrov, P. S.] (1896–1982)

1935 Sur les espaces discrets. C. R. Acad. Sci. Paris 200, 1649–1651.
1937 Diskrete Räume. Mat. Sb. 2 (44), 501–519.

Ball, Keith 1997 An elementary introduction to modern convex geometry. In: Flavors of Geometry, 1–58. Math. Sci. Res. Inst. Publ. 31. Cambridge: Cambridge University Press.

Bourbaki, Nicolas 1961 Topologie générale. Éléments de mathématique, première partie, livre III, chapitres 1 & 2. Third edition. Hermann.

Ghosh, Pijush K.; Kumar, K. Vinod 1998 Support function representation of convex bodies, its application in geometric computing, and some related representations. Computer Vision and Image Understanding 72, 379–403.

Halimskiĭ, E. D. 1970 Applications of connected ordered topological spaces in topology. Conference of Math. Departments of Povolsia.

1977 Uporyadochennnye topologicheskie prostranstva. Kiev: Naukova Dumka. 92 pp.

Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude 1993 Convex Analysis and Minimization Algorithms I. Fundamentals. Springer-Verlag, vxii + 417 pp.

Kaijser, Thomas 1998 Computing the Kantorovich distance for images. Journal of Mathematical Imaging and Vision 9, 173–191.

Kantorovich, L. 1942 On the translocation of masses. Comptes Rendus (Doklady) de l’Académie des Sciences de l’URSS 37, 199–201.

Khalimsky, Efim; Kopperman, Ralph; Meyer Paul R. 1990a Computer graphics and connected topologies on finite ordered sets. Topol. Appl. 36, 1–17.

1990b Boundaries in digital planes. J. Appl. Math. Stoch. Anal. 3, 27–55.

Kiselman, Christer O. 1981 How to recognize supports from the growth of functional transforms in real and complex analysis. In: Functional analysis, Holomorphy, and Approximation Theory (Ed. S. Machado); Lecture Notes in Mathematics 843, pp. 366–372. Springer-Verlag.

1991a Konvexa mängder och funktioner. Uppsala University, Department of Mathematics, Report No. 1991:LN1. 34 pp.

1991b Konveksaj aroj kaj funkcioj. Uppsala University, Department of Mathematics, Report No. 1991:LN2. 35 pp.

1996 Regularity properties of distance transformations in image analysis. Computer Vision and Image Understanding, 64, No. 3, 390–398.

2000 Digital Jordan curve theorems. Discrete Geometry for Computer Imagery, 9th International Conference, DGCI 2000, Uppsala, Sweden, December 13–15, 2000. (Eds. Gunilla Borgefors, Ingela Nyström, Gabriella Sanniti di Baja.) Lecture Notes in Computer Science 1953, pp. 46–56. Springer.

Kong, T. Y.; Rosenfeld, A. 1989 Digital topology: Introduction and Survey. Computer vision, graphics, and image processing 48, 357–393.

Kong, Yung; Kopperman, Ralph; Meyer, Paul R. 1991 A topological approach to digital topology. Amer. Math. Monthly 98, 901– 917.

Kuroš, A. G.

1962 Lekcii po obščej algebre. Moscow: F.M.

Rockafellar, R. Tyrrell

1970 Convex Analysis. Princeton, NJ: Princeton University Press.

Rosenfeld, Azriel

1979 Digital topology. Amer. Math. Monthly 86, 621–630.

Strömberg, Thomas

1996 The operation of infimal convolution. Dissertationes Math. 352. 58 pp.

Wyse, Frank, et al.

1970 Solution to problem 5712. Amer. Math. Monthly 77, 1119.

Author’s address: Uppsala University, Department of Mathematics,

P. O. Box 480, SE-751 06 Uppsala, Sweden.

Telephone: +46 18 4713216 (office); +46 18 300708 (home) Fax: +46 18 4713201

Electronic mail: kiselman@math.uu.se  URL: http://www.math.uu.se/~kiselman