Convex Geometry

Csaba Vincze

University of Debrecen, Hungary

Szerzői jog © 2013 University of Debrecen

TÁMOP-4.1.2.A/1-11/1 MSc Tananyagfejlesztés

Interdiszciplináris és komplex megközelítésű digitális tananyagfejlesztés a természettudományi képzési terület mesterszakjaihoz

2013

Előszó

A jelen digitális tananyag a TÁMOP-4.1.2.A/1-11/1-2011-0025 számú, "Interdiszciplináris és komplex megközelítésű digitális tananyagfejlesztés a természettudományi képzési terület mesterszakjaihoz" című projekt részeként készült el.

A projekt általános célja a XXI. század igényeinek megfelelő természettudományos felsőoktatás alapjainak a megteremtése. A projekt konkrét célja a természettudományi mesterképzés kompetenciaalapú és módszertani megújítása, mely folyamatosan képes kezelni a társadalmi-gazdasági változásokat, a legújabb tudományos eredményeket, és az info-kommunikációs technológia (IKT) eszköztárát használja.

Introduction

''The study of convex sets is a branch of geometry, analysis and linear algebra that has numerous connections with other areas of mathematics and serves to unify many apperantly diverse mathematical phenomena'' (Victor Klee).

Figure 1: Victor Klee, 1925-2007.

The systematic study of convex sets is a relatively young theory. The first monograph [10] was published by Bonnesen and Frenchel in 1934. In the middle of the 20th century lots of useful applications of convex sets were discovered. According to the importance of these applications convexity is a prosperous subject up to this day. In what follows we collectsome basic facts from the theory in different levels. The area of the material is the classical Euclidean space of dimension n. It is broad enough to include many of important applications. On the other hand this setting allows us to simplify many of the proofs.

The first chapter is divided into six sections 1.1-1.6. From 1.1 to 1.3 we summarize the elements of the linear algebra, topology, affine and convex sets to prepare the classical theorems of convex geometry. These are discussed in chapter 2 (Carathéodory's theorem) and chapter 3 (Radon's lemma and Helly's theorem). Refinements and generalizations such as the colorful Carathéodory's theorem due to I. Bárány [4] are also considered. The problem of separating and supporting hyperplanes can be found in chapter 7 to prepare the classical structure theorem of convex polyhedra (chapter 9) in the space of dimensionthree (vertices, edges, facets). The introductory level can be represented by the following diagram:

The mathematical prerequisites for the study of this level are linear algebra and basic point-set topology. Generalizations and applications can be found in chapters 4, 5, 6 and 8. Applications in the art gallery geometry are presented by Krasnosselsky's theorem (chapter 5) [37]. To illustrate that the study of convex sets has numerous connections with other areas of mathematics we tend to present some surprising applications such as affine [44] and convex [3] separations between functions (section 4.3). As a recent trend of the research we also refer to the problem of separation by members of a given linear interpolation family [46]. The common tool of these applications is the classical Helly's theorem and the proofs reflect the geometric feature of the problem. Kirchberger's theorem (chapter 8) [37] has a nice application in the approximation theory: how to find the best affine approximation for a given finite set of points. Another intensively studied area of the research is the generalization of the classical results for star-shaped sets (chapter 6). Among others the literature contains a star-shaped version of Krein-Milman's theorem [40] and Helly type theorems for intersections of star-shaped sets [15], [16] and [9]. Although Minkowski geometry is a very natural attached theory to convex sets it is only partially discussed in chapter 7 (section 7.3). It also appears in some applications (section 10.2). For lack of space another important parts of the theory are also missing. For example the study of inequalities concerning volumes of compact convex sets appears only as a subsection 4.2.1 or in connection with X-ray functions (section 10.3). Such kind of illustrative materials present new starting points for those interested in modern aspects of geometry [7]. Nowadays they are self-supporting branches of geometry together with basic monographs such as [53], [26] and [52]. The advanced course can be represented by the following diagram:

To take more steps forward we need some basic facts about metric properties of the space of convex compact sets and the foundations of the theory of convex functions (the natural domains for these functions are convex sets). We summarize them in the first chapter from 1.4 to 1.6. Chapters 10 and 11 present some special topics related to the convexity: Erdős-Vincze's theorem [24] and the theory of generalized conics.

The object of the generalized conics' theory (chapter 10) is the investigation of subsets in the space all of whose points have the same average distance from the set of foci. The "average" can be realized in several ways from classical (discrete) means to integration over the set of foci. In a significant part of typical situations the common feature of functions measuring the average distance is the convexity. They also satisfy a kind of growth condition. These properties imply that the (lower) level sets are compact convex subsets in the space bounded by compact convex hypersurfaces. They are called generalized conics. The most important discrete cases are polyellipses with the classical arithmetic mean to calculate the average Euclidean distance from the elements of a finite point-set and lemniscates (with the classical geometric mean to calculate the average Euclidean distance from the elements of a finite point-set). Lemniscates in the plane play a central role in the theory of approximation in the sense that polynomial approximations of holomorphic functions can be interpreted as approximations of curves with lemniscates. In terms of algebra we speak about the roots of polynomials (in terms of geometry we speak about the focuses of lemniscates). Endre Vázsonyi posed the problem whether the polyellipses (as the additive version of lemniscates) have the same approximating property by increasing the number of the foci or not. The answer is negative as a theorem due to P. Erdős and I. Vincze states. The proof can be found in chapter 11. In the literature we can find many generalizations of conics [47] and [30]. Computational difficulties are also significant in the theory. For the case of polyellipses see [23]. To computethe integral of the Euclidean distance along a curve to a given point is impossible in general. In case of a circle in the space we immediately have elliptic integrals. Nevertheless the best (recent) results [2] and [49] on elliptic integrals and Gaussian hypergeometric function allow us to develop a kind of theory of circular (generalized) conics [56], see also [57]. This is a partial motivation why to substitute the Euclidean distance with a more computable way of measuring the distance between the points in the space. Interesting applications in geometric tomography were found by measuring the average taxicab distance of points to a given subset. This is closely related to the coordinate X-ray functions (up to a multiplicative constant) which are typical sources of information about unknown bodies [26]. Beyond the (parallel or point) X-rays, projections and sections of sets we can also refer to the so-called angle function. The notion was introduced by J. Kincses [33] together with the problem of determination.

The last chapter is devoted to Radström's embedding theorem [48]. The theorem states that the collection of convex compact sets can be considered as a (convex) cone in an infinitely dimensional normed space, see also [17]. It is a natural idea to apply the calculus to volume, X-rays, anglefunctions etc. as mappings defined on the cone of convex compact sets. In many important particular cases we have nice properties. For example the Brunn-Minkowski inequality (for the concavity of the nth root of the n-dimensional Lebesgue measure) implies that the volume belongs to the class of quasi-concave functions having convex (upper) level sets. Another example (for coordinate X-rays) can be found in [58]. The last chapter of this material presents a new starting point of the investigation too.

1. fejezet - Elements

1.1 Linear Algebra

In what follows

(1.1)

is the standard real coordinate space of dimension n equipped with the canonical inner product

(1.2)

where

The elements of the coordinate space are called both vectors and points denoted by the symbols of the Latin alphabet in general. Especially we refer to the context for both terminology and notations. We speak about the norm

(1.3)

of vectors but the distance

(1.4)

between points. Mathematical objects labelled by indices will appear as v(1), ..., v(k) in text mode. The notation refers to the one-to-one correspondence between the set of indices and the set of objects labelled by them. Otherwise (in displayed mathematical formulas) we use

(1.5)

as usual. Let v and w be non-zero vectors in the coordinate space of dimension n and consider the auxiliary funtion

(1.6)

as t runs through the set of real numbers. Using the basic properties of the inner product it can be easily seen that the function 1.6 is a quadratic polynomial. Since the inner product is positive definite its discriminant must be less or equal than zero which leads to the so-called Cauchy-Buniakowsky-Schwartz inequality

(1.7)

The angle between non-zero vectors v and w can be defined as

(1.8)

in the usual way. According to inequality 1.7 the absolute value of the ratio between the inner product and the product of the norms must be less or equal than one. The system 1.5

(i) generates the vector space if each vector w can be written as the linear combination

(ii) is linearly independent if

implies that all of the coefficients are zero: λ(1)= ... =λ(k)=0.

Otherwise it is linearly dependent. Geometrically, the linear dependence means that we have a non-trivial polygonal chain with parallel sides to the vectors in the given system. Minimal generating systems (equivalently: maximal linearly independent systems) are called bases in the vector space. The common number of the members in minimal generating systems (maximal linearly independent systems) isthe dimension of the space. In this case each vector has exactly one expression as the linear combination of the members of the given system. The coefficients are called coordinates (with respect to the given basis). The canonical basis consists of the vectors

(1.9)

where the number 1 stands at the ith position and i=1, 2, ..., n. Recall that a non-empty subset in the space is a linear subspace if it is closed under the vector addition and the scalar multiplication. Especially, the dimension of the subspace

(1.10)

consisting of all linear combinations of the vectors in the argument is the rank of the system. It is clear that the rank is less or equal than k. Suppose that the vectors

are given in terms of the coordinates with respect to a basis

(1.11)

To decide the linear dependence (or independence) we have the following standard methods:

(i) The vanishing of a linear combination of the vectors

(1.12)

can be written as a system of linear equations

for the unknown coefficients

(1.13)

(ii) If the coordinates of the given vectors form the rows (or columns) of a matrix we can determine its rank which is just the same as the dimension of the generated subspace. If it is less than k then the system is linearly dependent. Otherwise (in case of rank k) the system is linearly independent.

(iii) In case of a square matrix we can calculate the determinant ofthe matrix for checking the linear dependence (the determinant vanishes) or independence (the determinant is different from zero). Especially any linearly independent (or generating) system containing exactly n vectors forms a basis in the coordinate space of dimension n.

1.2 Topology

Let r be a positive real number. The open ball around the point p with radius r is defined as the set of points all of whosedistance from p is less than r. A subset U in the space is open if for any point p in U is contained together with an open ball around p. In other words p is an interior point. A subset is closed if its complement is open. It can be easily seen that

(T1) both the empty set and the entire space are open (and, at the same time, they are closed).

(T2) the union of the elements of an arbitrary family of open subsets is open.

(T3) the intersection of finitely many open subsets is open.

In general the family of subsets satisfying conditions (T1)-(T3) is called topology. The members of the topology are the open subsets. The topology has a countable basis if there exists a countable collection

(1.14)

of open subsets such that for any open subset can be written as the union of the elements of some subcollection. It is just the second axiom of countability and the space equipped with a topology having a countable basis is called second-countable space.

Example The Euclidean space of dimension n is a second countable space because the collection of open balls having centers with rational coordinates and positive rational numbers as radiuses forms a basis for the usual topology.

An open cover of a subset A is a family of open subsets containing A in the union of its elements. The subset A is compact if every open cover contains a finite subcover. It is known (see Heine-Borel theorem) that the compactness is equivalent to the boundedness and closedness in the real coordinate spaces. A subset is bounded ifit is contained in an open ball around the origin with a finite radius.

Definition The closure of a subset A in a topological space is the intersection of closed subsets containing A. The interior of A is the union of open subsets contained in A.

Figure 2: Ernst Leonard Lindelöf, 1870-1945.

Theorem 1.2.1 (Lindelöf, Ernst Leonard) Every open cover in a second-countable space contains a countable subcover.

• Consider an arbitrary open cover of the subset A in a second-countable topological space:

(1.15)

where U(1), ..., U(m), ... is a basis of the topology and

(1.16)

If I is the union of I(γ) as γ runs through the set Γ then it is a countable set of indices. Equation 1.15 shows that A is a subset in the union of U(i)'s as i runs through the set I. Since for any i there exists γ(i) such that U(i) is a subset in V(γ(i)) we have that

and the subcollection

is a countable open subcover for the subset A as was to be proved. ▮

1.3 Affine and convex sets

Definition The linear combination

(1.17)

is affine if the sum of the coefficients is just one:

(1.18)

Convex combinations are affine combinations with non-negative coefficients.

The affine combination of vectors commutates with translations in the sense that the affine combination of the translated vectors is the translate (with the same vector) of the affine combination (with the same coefficients):

because of 1.18. In a similar way affine transformations preserve the affine combinations of the elements.

Definition The set l(p,q) consisting of the elements of the form

(1.19)

is the affine line joining the points p and q. The set s(p,q) consisting of the elements of the form

(1.20)

is the segment joining the points p and q.

Remark Affine lines/segments are the set of all affine/convex combinations of two elements in the space.

Definition A subset in the space is called affine or convex if it contains all the affine lines or segments joining its points.

Remark It will be convenient to consider the empty-set and singletons, i.e. subsets containing at most one element as both affine and convex sets.

Proposition 1.3.1 A subset is affine if and only if it contains all of the affine combinations of its elements.

Proof The statement is trivial for subsets containing at most one element. Otherwise if a subset A contains all of the affine combinations of its elements then, especially, it contains the points of any affine line joining them. Conversely let A be an affine set. The proof is based on a simple induction by the number of the elements in the affine combination. The case of k=1 is trivial. If k=2 then we can use directly the definition of the affine set. Suppose that the statement is true for affine combinations containing at most k - 1 vectors and consider the affine combination

of the elements

Because at least one of the coefficients must be different from 1 we can write, for example, that

where

is in A because of the inductive hypothesis and

is an expression for v as an affine combination of two elements from the affine set A. Therefore v is in A as was to be proved. ▮

Proposition 1.3.2 A subset is convex if and only if it contains all of the convex combinations of its elements.

Proof The statement is trivial for subsets containing at most one element. Otherwise if a subset K contains all of the convex combinations of its elements then, especially, it contains the points of any segment joining them. Conversely let K be a convex set. The proof is based on a simple induction by the number of the elements in the convex combination. The case of k=1 is trivial. If k=2 we can use directly the definition of the convex set. Suppose that the statement is true for convex combinations containing at most k - 1vectors and consider the convex combination

of the elements

Because at least one of the coefficients must be different from 1 we can write, for example, that

where

is in K because of the inductive hypothesis and

is an expression for v as a convex combination of two elements from the convex set K. Therefore v is in K as was to be proved. ▮

Consider the collection of all linear combinations of the elements from H. It is called the linear hull (c.f. generated subspace) of the subset H. From the elements of the linear algebra it is well-known that the linear hull is a linear subspace.In what follows we present the corresponding results in case of the affine and convex hulls.

Definition The affine hull/affine envelope aff H is the collection of all affine combinations of the elements from H.

Theorem 1.3.3 The affine hull is an affine set.

Proof Let

be two elements from aff H. Any point z=(1 - λ)p+λq of the affine line joining p and q is the affine combination of the elements

in H because

and the sum of the new coefficients is just one:

Thereore z is in aff H as was to be proved. ▮

Definition The convex hull/convex envelope conv H is the collection of all convex combinations of the elements from H.

Theorem 1.3.4 The convex hull is a convex set.

Proof Let

be two elements from conv H. Any point z=(1 - λ)p+λq of the segment joining p and q is the convex combination of the elements

in H because

and the sum of the new (non-negative) coefficients is just one:

Thereore z is in conv H as was to be proved. ▮

Excercise 1.3.5 Prove that the intersection of affine/convex subsets is affine/convex.

Corollary 1.3.6 The affine hull aff H is just the intersection of affine sets containing H.

Corollary 1.3.7 The convex hull conv H is just the intersection of convex sets containing H.

Theorem 1.3.8 (Characterization of affine sets). Each non-empty affine set A can bewritten into the form A=p+L, where p is an arbitrary point in A and L is a uniquely determined linear subspace.

Proof Since A is non-empty choose a point p in A and let us define the translated set L= - p+A. The origin belongs to L because p is in A. We are going to prove that L is closed under the vector addition and the scalar multiplication which implies that it is a linear subspace. Let v(1), ..., v(k) be elements in L, i.e.

for some elements w(1), ..., w(k) from A. Then

and v is in L because w is the affine combination of the elements p, w(1), ..., w(k) from the affine set A. To clarify that L is uniquely determined suppose that p+M=q+L for some points p, q and linear subspaces M, L. Translate with the additive inverse of p it follows that M=q - p+L. Since the origin must be an element of each linear subspace (especially M) we have that the difference vector of p and q is also in L. Here L is a linear subspace which is closed under the vector addition and thus

as was to be proved. ▮

According to the previous theorem non-empty affine sets are often called affine subspaces on the model of the linear subspaces.

Definition The dimension of a non-empty affine set is just the dimension of the associated linear subspace. In case of a subset H the dimension is defined as the dimension of its affin hull. The empty-set is of dimension - 1.

1.4 Operations with sets

Definition The sum of non-empty sets A and B is defined as the set

In case of translated linear subspaces (affine sets) the symbol + has been used in the same sense. The product of a set and a real number is

From the viewpoint of geometry the scalar multiplication is a central similarity (with the origin as the center), the addition is the union of images of A under translations with the elements of B (and vice-verse):

(1.21)

This means that the scalar multiplication obviously preserves the convexity.

Theorem 1.4.1 The sum of convex sets is convex.

Proof If one of the terms is a singleton then the statement is trivial because the translation preserves the convexity. Otherwise let

be two elements of the set A+B, where

Then

Because of the convexity

Therefore

as was to be proved. ▮

Proposition 1.4.2 Addition and scalar multiplication of sets have the following properties:

(1.22)

(1.23)

We also have the following distributivity-like property:

(1.24)

If A is convex and the scalars have a common sign then

(1.25)

Finally

(1.26)

and

(1.27)

Proof Properties 1.22, 1.23, 1.24, 1.26 and 1.27 are trivial in the sense that they are direct consequences of the addition and the scalar multiplication of vectors. If one of the scalars is zero then property 1.25 is also obvious. Consider the case of positive scalars to prove one of the non-trivial cases (the case of negative scalars is similar). Suppose that

for some element v in A. Then

showing that the inclusion

(1.28)

holds without any extra condition. Conversely if

then we can write z into the form

where the right hand side involves not necessarily the same elements from A. Then we have that

The right hand side is a convex combination of elements from a convex set. Therefore

and property 1.26 says that

as was to be proved. ▮

Proposition 1.4.3 (Cancellation law, first version) If A, B and C are non-empty sets such that B is closed and convex, C is bounded then

implies that

Proof Consider an element a in A and choose a point c(1) in C. Because of our hypothesis there exist

Similarly

for some elements b(2) in B and c(3) in C. In the kth step we have that

(1.29)

Taking the sum of equations 1.29 as k runs from 1 to n we have that

and, consequently,

Since C is bounded

and thus

where the right hand side involves a sequence of convex combinations of elements in B. Therefore the sequence runs in B (convexity) and its limit belongs to B because of the closedness. ▮

Corollary 1.4.4 (Cancellation law, second version) If A, B and C are non-empty sets such that A and B are closed and convex, C is bounded then

implies that A=B.

Remark The collection of non-empty compact convex sets forms a cancellative semigroup with respect to the set-addition.

1.5 The Hausdorff distance

Definition Let A be a non-empty compact set in the space. The parallel body P(A, λ) to A with radius λ > 0 is A+λD, where D denotes the closed unit ball around the origin.

Figure 3: Felix Hausdorff,1868-1942.

Lemma 1.5.1 The parallel bodies of a non-empty compact set A are compact.

Proof The boundedness is clear. To prove that A+λD is closed choose a point p in the complement. This means that for any point a in A the distance between p and a is greater than λ. Using excercise 1.7.31 (iii) it follows that

(1.30)

and the same holds for the elements of an open neighbourhood of p with a sufficiently small radius. Therefore the complement of the parallel body is open and, consequently, the parallel body is closed.

Definition The Hausdorff distance between two non-empty compact sets A and B in the space is defined as

Remark According to the compactness the set of positive reals satisfying

is non-empty and

Proposition 1.5.2 The Hausdorff distance is a metric on the collection of non-empty compact subsets in the space, i.e. it is positive definite

symmetric

and satisfies the triangle inequality

Proof The non-negativity of the Hausdorff distance is trivial. To prove the non-trivial part of the positive definiteness suppose that we have two different sets A and B such that there exists a point p from A which is not in B. Especially B is closed which means that its complement is open. The point p is contained in the complement of B together with an open ball centered at p with radius λ. Therefore

(1.31)

By contraposition

Changing the role of A and B we have that h(A,B)=0 implies that A=B. The symmetry is trivial. To prove the triangle inequality observe that

and thus

On the other hand

and thus

Therefore

as was to be proved. ▮

Proposition 1.5.3 (The minimax characterization) Let A and B be non-empty compact sets and

and

Then

Proof Since A is contained in the parallel body of B with radius h(A,B) it follows that

for any a in A. Taking the maximum as a runs through the points of A we have that λ(1) is less or equal than h(A,B). So is λ(2) by changing the role of A and B:

From the definition of λ it follows that A is a subset in B+λD and B is a subset in A+λD. Therefore

Finally λ=h(A,B) as was to be proved. ▮

Figure 4: The minimax characterization.

Figure 5: The minimax characterization.

Theorem 1.5.4 The space of non-empty compact subsets in the coordinate space of dimension n equipped with the Hausdorff metric is a complete metric space.

Proof Let A(1), A(2), ..., A(m), ... be a Cauchy sequence with respect to the Hausdorff metric. The first observation is that it is uniformly bounded, i.e. there exists a solid sphere containing all the elements of the sequence. To prove the existence of such a body let ε > 0 be a given positive real number. Then there exists a natural number N such that

This means that that A(m) is a subset of the parallel body of A(N+1) with radius ε. On the other hand we can take the maximal distance among the missing finitely many elements A(1), ..., A(N) of the sequence from A(N+1). If

then all the elements of the sequence is contained in any solid sphere G containing the parallel body P(A(N+1),d). As a second step let B(k) be the closure of the union

It is clear that B(k)'s are non-empty compact subsets in the space (compactness is clear because of Heine-Borel's theorem via uniform boundedness) and they form a decreasing nested sequence, i.e. B(k+1) is a subset in B(k). Therefore[1]

Moreover B is compact. We prove that B(k) tends to B with respect to the Hausdorff metric. Since

we have

This means that the sequence of the Hausdorff distances is monotone decreasing and bounded from below. Therefore it is convergent and the limit is just the infimum as k runs through the natural numbers. Suppose, in contrary, that the infimum is strictly positive. Then we can choose an element p(k) of the corresponding B(k) such that

for any natural number k. Taking a convergent subsequence with the limit point p it follows that

But p must be in B because B(k) is a decreasing nested sequence of compact sets and thus p must be in B(k) for any natural number k. This is obviously a contradiction. By the definition A(k) is a subset in B(k) which implies (together with the previous convergence B(k) --> B) that A(k) is a subset of the parallel body to B with radius ε provided that k is great enough. To prove the converse relationship we use that A(k) is a Cauchy sequence. This means that if k is great enough then

and, consequently,

because the set on the right hand side is compact (especially closed) and contains each member of the union: recall the minimality property of the closure of a set.

Using that central similarities are circle-preserving transformations the property

(1.32)

is trivial without any extra condition. The following proposition shows that the Hausdorff distance also has a natural behavior under ''translations'' in case of non-empty compact convex sets.

Proposition 1.5.5 (Invariance under ''translations''.) If A, B and C are non-empty compact convex sets in the space then

Proof For the sake of simplicity let

Since

it follows that

showing that

Conversely

which implies by the first version of the cancellation law 1.4.3 that

showing that

Therefore

as was to be proved. ▮

1.6 Convex functions

In what follows let K be a non-empty open convex subset in the coordinate space of dimension n and consider a function

(1.33)

Definition The function f is convex if for any points p and q in K

(1.34)

where λ is in [0,1]. The function f is concave if - f is convex.

The geometric meaning of equation 1.34 is that chords joining the points on the graph are above it. This can be expressed in terms of the so-called epigraph as the following theorem shows.

Figure 6: The epigraph of a function.

Proposition 1.6.1 The function f is convex if and only if itsepigraph

is a convex subset in the coordinate space of dimension n+1.

Proof Let f be a convex function and suppose that (p,t) and (q,s) are in epi f. Then

where v:=(1 - λ)p+λq is in K because of its convexity and the scalar "coordinate" satisfies the inequalities

because of the convexity of the function. Therefore epi f is convex (as a set). Conversely, if epi f is a convex set then the chords joining its boundary points are "above" the graph of f and inequality 1.34 follows immediately. ▮

Proposition 1.6.2 (Jensen, Johan) The function f is convex if and only if

(1.35)

for any convex combination of elements from K.

Proof Inequality 1.35 gives the definition of convex functions under the special choice k=2. Conversely, if a function is convex then inequality 1.35 is satisfied in case of k=2 because of the definition of convex functions (if k=1 then there is nothing to prove). For convex combinations involving more that two terms the proof is based on a simple induction. Suppose that 1.35 is true for convex combinations containing at most k - 1 vectors and consider the convex combination

of the elements v(1), ..., v(k) in K. Because at least one of the coefficients must be different from 1 we can write, for example, that

where

is in K because of its convexity and

Then

(1.36)

and, by the inductive hypothesis,

(1.37)

Relations 1.36 and 1.37 give that

as was to be proved. ▮

Figure 7: Johan Jensen, 1859-1925.

Proposition 1.6.3 Let K be a non-empty open convex set. If the function

is convex then it is continuous at any point in K.

Proof Let p in K be a given point (recall that K is a non-empty open convex subset). Without loss of generality we can suppose that p is just the origin 0. As the first step we are going to prove that f is locally bounded. Consider an open box R of dimension n centered at the origin in K. Since the elements in R can be expressed as a convex combination of the vertices

we have that for any v in R

where

On the other hand

where - v is in R because the origin is the center of the box. Using the upper bound M and the convexity of the function

and, consequently,

is a lower bound. Therefore

Figure 8: The proof of Proposition 1.6.3.

In the second step we claim that f is locally Lipschitzian. Consider an open ball B centered at p with radius r such that 2B is contained in the box R. Then for each q in B we have a point z not in B but in R such that

Explicitly

where

is the simple ratio among the points. Using the convexity of the function we have that

and, consequently,

(1.38)

because z is not in B but z is in R. Therefore

(1.39)

Using the same argumentation as above for the triplet q, p and u:= - z we have that

(1.40)

and, consequently,

The last equation allows us to present a lower estimation

(1.41)

Therefore

(1.42)

Inequalities 1.39 and 1.42 say that

i.e. the function is locally Lipschitzian and, consequently, it is continuous at p as was to be proved. ▮

Figure 9: Rudolf Lipschitz, 1832-1903.

Inequalities 1.38 and 1.42 imply more than the continuity: the existence of the one-sided directional derivatives

at each point into each direction. Indeed, consider the function

defined on a sufficiently small open interval. Using the notation q=p+tv inequality 1.42 says that h is bounded from below. Taking t < s and z=p+sv 1.38 shows that h is monotone increasing. Therefore its infimum M*=inf h exists and

For further regularity properties of convex functions see Lebesgue's theorem and [8]. Figure 10 shows why it is important for the point p to be in the interior of the domain.

Figure 10: Discontinuity on the boundary of the domain.

Definition The element w is called a subgradient of the function f at the point p in K if the inequality

(1.43)

holds for any point q in K. The subdifferential of the function f is the set of its subgradients.

For the geometric description of a subgradient vector write inequality 1.43 into the form

to express that the graph of the function must be entirely above the hyperplane

(1.44)

passing through the point (p, f(p)) in the coordinate space of dimension n+1. The vector (w, - 1) plays the role of the normal vector to the hyperplane 1.44.

Figure 11: The subgradient vector.

The subgradient involves a global property whereas the derivative has a local character. Nevertheless the convexity of the function allows us to describe the set of subgradients locally in terms of the directional derivative.

Proposition 1.6.4 (Local characterization.) Let K be a non-empty open convex set and consider a convex function

The element w is a subgradient at the point p in K if and only if the inequality

holds for any element v in the coordinate space.

Proof Suppose that w is a subgradient of the function f at the point p and let us choose the point q in the special form

where v is a nonzero vector and t is a positive real number which is small enough for q to be in K. Then the relation

follows immediately from the definition of the subgradient. Therefore

In order to see the converse statement let q be an arbitrary point in K and consider the line segment

joining p and q. Since the function is convex, the formula

holds for any parameter t between 0 and 1. Therefore

This means that

implies that

as was to be proved. ▮

Corollary 1.6.5 Let K be a non-empty open convex set and consider a convex function

The following conditions are equivalent:

• The point p in K is a global minimizer.

• The zero vector 0 belongs to the subdifferential of f at p.

• For any element v

Proof If p is a global minimizer then for any q in K

showing that 0 is one of the subgradient at p. If 0 is one of the subgradient at p then, by definition

and we have that p is a global minimizer. The equivalence of (ii) and (iii) is a direct consequence of the local characterization Proposition 1.6.4 of the subgradient vectors. ▮

Figure 12: The zero vector as a subgradient.

Definition Suppose that

is differentiable at the point p. The gradient vector is defined in terms of the usual partial derivatives:

Actually it is a special notation for the Jacobian matrix at the point p.

For the sake of simplicity we restrict ourselves to the coordinate plane to present the geometric characterization of the gradient vector. We will use the standard symbols x and y for the coordinates of the points in the plane. Let U be a non-empty open subset and consider a (not necessarily convex) function

Suppose that f is continuously differentiable, i.e. it is differentiable everywhere and the partial derivatives are continuous. Let p be a point in U with a non-zero gradient vector. This means, for example, that the partial derivative with respect to the second coordinate at p is different from zero:

Let us define the mapping

The Jacobian

is different from zero at p.

Figure 13: The inverse mapping theorem.

Using the inverse mapping theorem we have an inverse function defined on an open neighbourhoof Φ(V) of Φ(p). We are going to give a local parameterization for the level curve

(1.45)

passing through the point p. Let r be a sufficiently small positive real number such that

is a parametrization of the horizontal segment passing through Φ(p) and t is between r and - r. Then

is just a local parametrization of the level curve 1.45 because

Therefore

(1.46)

which means that the gradient vector field along the level curves is orthogonal to the tangent lines represented by the derivative vector w'.

Figure 14: The gradient vector.

Remark In case of higher dimensional spaces the gradient vectors are orthogonal to the tangent hyperplanes of the level hypersurfaces.

1.7 Excercises

Excercise 1.7.1 Find the parameter t for the system

to be linearly dependent. Prove that in case of t=1 the system is linearly independent and find the coordinates of

with respect to the basis

Excercise 1.7.2 Find the inverse of the matrix

How the inverse matrix is related to the coordinate transformation?

Excercise 1.7.3 Find the parameters t and s for the system

to be linearly dependent. What is the locus of points with coordinates t and s in the plane.

Excercise 1.7.4 Find the rank of the systems

Excercise 1.7.5 Find the rank of the systems

Excercise 1.7.6 Find the inverse of the matrices

and solve the equation

To calculate the distance between a point and a linear (or affine) subspace[2] H in the Euclidean space one typically needs the orthogonal complement to H. Especially systems consisting of pairwise orthogonal non-zero vectors play a distinguished role in Euclidean geometry (see Gram-Schmidt's process of orthogonalization). The following excercises refer to some special tools and process in the coordinate space of dimension three. Problems in higher dimensionalspaces will be also formulated.

Excercise 1.7.7 Calculate the vectorial product of the elements

in the coordinate space of dimension three. Is the resulting vector perpendicular to the terms of the product? How to express its length in terms of lengths of the given vectors and the angle between them? What about the orientation of the system

Excercise 1.7.8 Calculate the mixed product of the elements

Excercise 1.7.9 Calculate the distance between the point

and the plane

Excercise 1.7.10 Calculate the distance between the point

and the line

Excercise 1.7.11 Calculate the distance between the lines

and

Excercise 1.7.12 Calculate the distance between the point

and the affine subspace given by the system of equations

Excercise 1.7.13 Calculate the distance between the point

and the affine subspace given by the system of equations

Excercise 1.7.14 Prove that the formal determinant of the matrix

where the first row contains the members of the canonical basis 1.9 gives a vector perpendicular to every element of the system

Excercise 1.7.15 Use the standard Gram-Schmidt process to transform the system

into an orthogonal system of vectors. How to compute the coordinates of

with respect to a basis consisting of pairwise orthogonal unit vectors.

Excercise 1.7.16 Use the standard Gram-Schmidt process to transform the following systems into orthogonal ones in the generated linear subspaces.

Find the missing vectors to give orthogonal bases in the coordinate space of dimension four.

Although vector spaces of the same finite dimension are isomorphic sometimes they have lots of different features relative to the standard coordinate space of dimension n. To finish this section we formulate some excercises related to vector spaces of different objects to illustrate how the presented technics and methods work in strange situations.

Excercise 1.7.17 Prove that the set of square matrices of order n forms a Euclidean vector space with respect to the inner product

where the operator T refers to the transpose of the matrix.

Excercise 1.7.18 Prove that the set of polynomials of order at most n forms a Euclidean vector space with respect to the inner product

Use the standard Gram-Schmidt process to transform the system of monomials

into an orthogonal system of polynomials; see Legendre polynomials.

Excercise 1.7.19 Prove that for every Euclidean vector space v and w are perpendicular to each other if and only if

(1.47)

Hint. Formula 1.47 is just the generalization of the classical Pythagorean theorem (and its converse).

Figure 15: Legendre polynomials up to order four.

Excercise 1.7.20 Prove that for every Euclidean vector space the elements v and w have the same length if and only if the sum of the given vectors is perpendicular to the difference vector.

Hint. The diameters of a rhombus are perpendicular to each other.

One of the most important relationships in Euclidean vector spaces is the so-called parallelogram-law

It can be easily derived from the characteristic properties of the inner product: additivity and homogeneity in each of the variables, symmetry and positive definiteness. Actually it is a necessary and sufficient condition for the existence of an inner product corresponding to a given norm. Recall that the norm provides an adequate way to measure the length of vectors in the space. This means non-negativity and positive definiteness, absolute homogeneity and subadditivity (in an equivalent terminology: triangle inequality).

Excercise 1.7.21 Using the parallelogram law prove that the norm

does not come from any inner product. What about the so-called taxicab norm

(1.48)

Using the associated distance function

(1.49)

in the coordinate plane sketch the "ellipse"

and find its perimeter.

Hint. The equation of the ellipse is

with perimeter 12 (with respect to the associated distance function 1.49).

Excercise 1.7.22 Prove or disprove the following statements:

• The intersection of open/closed subsets is open/closed.

• The union of closed subsets is closed.

• The intersection of compact subsets is compact.

Excercise 1.7.23 Prove that for any subset A in a topological space the collection of sets of the form

(1.50)

where U is open in the embedding space forms a topology for A.

Hint. The set A equipped with the so-called relative topology 1.50 is called a subspace of the embedding topological space.

Excercise 1.7.24 Let A be a subset all of whose convergent sequences tend to an element in A. Prove that A is closed. Prove the converse of the statement in case of subsets in the real coordinate space of dimension n.

The following excercise contains the topological characterization of the continuity of a mapping

(1.51)

at the point p of its domain. For the sake of simplicity let q:=f(p) be the image of p under f.

Excercise 1.7.25 Prove that the mapping 1.51 is continuous at p if and only if for every open neighbourhood V around q there exists an open neighbourhood U around p such that f(U) is a subset in V.

Hint. Suppose that the topological characterization is true and let p(k) be a sequence tending to p. If r is an arbitrary positive real number and V is the open ball around f(p) with radius r then, by our assumption, there exists an open neighbourhood U around p such that f(U) is a subset in V. Since p is an interior point of U it follows that p(k) is in U provided that k is great enough. Therefore f(p(k)) is in V showing that f(p(k)) tends to f(p). To prove the converse of the statement let V be an open neighbourhood around q and suppose in contrary that for any integer k the open ball U(k) around p with radius (1/k) contains an element f(p(k)) which is not in V. To present the contradiction it is enough to consider the limit of f(p(k)) as k tends to the infinity.

Excercise 1.7.26 Prove that the mapping 1.51 is continuous if and only if for every open set in the coordinate space of dimension m the pre-image under the mapping f is an open set in the coordinate space of dimension n.

Excercise 1.7.27 How the pre-image/image of the union of subsets A and B is related to the union of pre-images/images of A and B.

Excercise 1.7.28 How the pre-image/image of the intersection of subsets A and B is related to the intersection of pre-images/images of A and B.

Definition The final topology (the strong topology with respect to f) of the coordinate space of dimension m is defined by the collection of subsets for which the pre-images under the mapping 1.51 are open in the usual sense. The initial topology (the weak topology with respect to f) of the coordinate space of dimension n is defined by the collectionof subsets for which the images under the mapping 1.51 are open in the usual sense.

Excercise 1.7.29 Prove that both the final and the initial topology satisfy conditions T1, T2 and T3.

Excercise 1.7.30 Prove or disprove the following statements:

• the image of an open set under a continuous mapping is open,

• the pre-image of a closed set under a continuous mapping is closed,

• theimage of a compact set under a continuous mapping is compact.

Excercise 1.7.31 Let A be a compact subset in the real coordinate space of dimension n. Prove that

• A is closed and bounded.

• Every sequence in A has a convergent subsequence.

• Every continuous function on A attains both its minimum and its maximum.

Excercise 1.7.32 How the closure/interior of the intersection of A and B isrelated to the intersection of the closures/interiors of A and B.

Excercise 1.7.33 How the closure/interior of the union of A and B is related to the union of the closures/interiors of A and B.

Excercise 1.7.34 Prove that both the interior and the closure of a convex set are convex.

Excercise 1.7.35 Find the convex hull of three not collinear points in the space.

Excercise 1.7.36 Find theconvex hulls of the following subsets in the plane:

Hint. See epigraphs of functions; proposition 1.6.1.

Excercise 1.7.37 Find the convex hull of the set y=sin x in the plane.

Excercise 1.7.38 Find the convex hulls of the following subsets in the plane:

Hint. In case of the cubic function prove that any point (x,y) in the plane can be written as

i.e. as a trisection of a segment joining two points on the graph. (Use the fundamental theorem of algebra to prove that a real polynomial of order three always has a real root).

Excercise 1.7.39 Find the equation of the affine hull of the elements

Hint. To find the equation of the affine hull choose the point p(1) as the "origin" and consider the linear subspace L spanned by the position vectors

with respect to p(1). It can be easily checked that the orthogonal complement is generated by

and the equation of the affine hull is just

The right hand side is created in the only possible way to provide p(1) as the element of the affine hull.

Excercise 1.7.40 Find the equation of the affine hull of the elements

Excercise 1.7.41 Find the dimension of the affine hull of the elements

Excercise 1.7.42 Find the dimension of the affine hull of the elements

Excercise 1.7.43 Prove that if A and B are affine sets with a non-empty intersection then

What about the dimension of the union of disjoint affine subsets?

Hint. The formula for the dimension of the union of intersecting affine subsets is just the same as the usual one for linear subspaces. But the condition of a non-empty intersection is important as the case of parallel lines in the coordinate space of dimension three shows. Here is the only big difference between affine and linear subspaces: two linear subspaces always meet in the origin of the space. The translation part varies the possible positions of an affine subspace relative to another one (see e.g. parallelism).

Excercise 1.7.44 Find the sets

where A, B and C are the segments joining the points

in the plane, respectively.

Figure 16: Addition of sets.

Figure 17: Addition of sets.

Excercise 1.7.45 Find the sum of the sets A and D, where A is the segment joining the points

and D is the unit disk centered at the origin, cf. the definition of parallel bodies 1.5.

Figure 18: Addition of sets.

Excercise 1.7.46 Find the sum of the sets A and B, where

and B is the closed unit disk given by the inequality

Figure 19: Addition of sets.

Figure 20: Addition of sets.

Excercise 1.7.47 Why distributivity-like property 1.25 is not true in general?

Excercise 1.7.48 Prove the subbaditivity

(1.52)

and the homogenity

(1.53)

of the conv - operator.

Excercise 1.7.49 Why the cancellation laws are false in general?

Hint. Let C be the unit disk centered at the origin and consider its boundary B. Since B+C is the union of unit disks centered at the points of B we have that B+C=2C (the disk centered at the origin with radius 2). If A={ 0} then A+C is obviously a subset in 2C=B+Cbut 0 is not in B.

Excercise 1.7.50 Find the parallel body of a point, a segment and a polygonal chain in the plane, see figure 18.

Excercise 1.7.51 Prove that

What about the converse of the statement?

Excercise 1.7.52 Prove that if A is a non-empty compact convex set then

Excercise 1.7.53 Express the Hausdorff distance between closed disks in the plane in terms of the radius and the distance between the centers.

Excercise 1.7.54 Let

and C be the closed unit disk given by the inequality

Calculate the Hausdorff distances among the given subsets in the coordinate plane.

Excercise 1.7.55 Prove that any two of the segments forming the sides of a square in the plane have the same Hausdorff distance.

Excercise 1.7.56 Prove that the operator conv is Lipschitzian, i.e.

(1.54)

Hint. Since

it follows from the subadditivity 1.52 and the homogenity 1.53 that

In a similar way

proving equation 1.54.

Excercise 1.7.57 Prove that the collection of non-empty convex compact subsets is a closed set in the metric space of non-empty compact sets equipped with the Hausdorff metric, i.e. the limit of a convergent sequence of compact convex subsets is convex.

Hint. Use the Lipschitzian property 1.54 to prove that if A(k) tends to B then conv A(k) tends to conv B.

Excercise 1.7.58 Find examples to present the strict inequality

(1.55)

Excercise 1.7.59 Prove that Hausdorff metrics related to different compact convex "unit" bodies containing the origin in their interiors are equivalent to each other.

Excercise 1.7.60 Prove that equality holds in 1.34 for any real number λ if and only if

is a linear functional.

Excercise 1.7.61 Prove that the set of convex functions with a common domain forms a convex cone, i.e. it is closed under the addition of functions and the multiplication with non-negative scalars.

Excercise 1.7.62 Prove that the lower level sets defined by the inequality

are convex in case of a convex function. Prove that the upper level sets defined by the inequality

are convex in case of a concave function. What about the converse statements?

Hint. Consider revolution surfaces as graphs of functions to illustrate that convex (lower) level sets do not guarantee the convexity in the sense of 1.34 (functions with convex lower level sets are called quasi-convex).

Excercise 1.7.63 Find the convex functions in the following list:

How the convexity of invertible continuous functions with one variable and their inverses are related?

Hint. Using Bolzano's theorem prove that invertible continuous functions are strictly monotone. How the convexity of a strictly monotone increasing function and its inverse are related?

Excercise 1.7.64 Find the convex functions in the following list:

Excercise 1.7.65 Find the parameters a and b for the function

to be convex on the entire real line.

Excercise 1.7.66 Let

be a convex function. Prove that

is non-decreasing.

Excercise 1.7.67 Prove that the subgradient vectors form a convex set.

Excercise 1.7.68 Find the subgradient vectors of the function

at the origin.

Hint. If w is a subgradient vector at the origin then, by definition,

in the first quadrant of the coordinate plane. Therefore

which means that (1 - w(1),1 - w(2)) must be also in the first quadrant. Therefore

Using the same technic in the further quadrants of the plane we have that the subgradient vectors form the set

Excercise 1.7.69 Prove that the minimizers of a convex function form a convex set.

Definition The function f is strictly convex if

for any different points p, q and real number 0<λ<1. In other words equality in 1.34 can be realized only in trivial ways: either p=q or λ=0 or 1.

Excercise 1.7.70 Prove that a strictly convex function has at most one minimizer.

In the theory of convex functions there are several methods to generate new convex functions from given ones (operations). The following examples are devoted to illustrate some of them.

Definition Let f(1), ..., f(m) be given real-valued functions on the same domain in the coordinate space of dimension n. By taking the pointwise maxima we define the max function as follows:

Especially,

Excercise 1.7.71 Prove that the max-function of convex functions is convex.

Figure 21: The max-function.

Using the sum of (strict) epigraphs as convex sets in the coordinate space of dimension n+1 we can create a new (strict) epigraph together with a new function. It will be convex because the sum of convex sets is convex. This leads to the notion of infimal convolution of convex functions(see also conjugation).

Excercise 1.7.72 Find the analytic description of the infimal convolution of convex functions.

Hint. In case of real functions

Excercise 1.7.73 Find the gradient vectors of the following functions

Excercise 1.7.74 Find the equation of the tangent lines to the following plane curves at the given points:

Excercise 1.7.75 Find the equation of the tangent line to the following plane curve at the given point:

2. fejezet - Carathéodory's theorem

In section 1.3 of the previous chapter we defined the affine and the convex hull of a set as the collection of affine and convex combinations of the elements. The structure theorem 1.3.8 of affine sets allows us to generate the affine hull with the help of foundations of classical linear algebra: the problem is how to determine the associated linear subspace of the affinehull. Let H be an arbitrary non-empty subset in the coordinate plane. Theorem 1.3.8 says that the affine hull aff H can be written into the form p+L, where p is in H and L is a uniquely determined linear subspace. Let p in H be an arbitrary point and consider a maximal linearly independent system of vectors

(2.1)

where w(1), ..., w(k) are in H. Elements in 2.1 can be interpreted as position vectors of w's with respect to the base point p. Suppose that the orthogonal complement N to the generated linear subspace of 2.1 is spanned by

(2.2)

The element w belongs to the affine hull of H if and only if the position vector w - p is orthogonal to all the vectors z(k+1), ..., z(n). Therefore we have n - k equations

(2.3)

to characterize the affine hull of H. The linear independence of the system 2.1 is equivalent to the affinely independence of p, w(1), ... w(k). As another way to prepare (and motivate) the central notion of affinely independence/dependence in the forthcoming sections suppose that

where both sides of the equation involve combinations of the same type (affine or convex). For the definiteness consider the case of affine combinations:

We have

i.e. the system

is linearly dependent in such a way that the sum of the coefficients is equal to zero.

2.1 Affinely dependence and independence

Definition The system

(2.4)

of vectors is affinely dependent if the zero vector can be expressed as a non-trivial linear combination

(2.5)

such that the sum of the coefficients is zero:

(2.6)

The system is affinely independent if it is not affinely dependent.

Remark Affine dependence involves the linear dependence of the system together with an additional requirement 2.6 for the coefficients.

Corollary 2.1.1 The system 2.4 is affinely dependent if and only if

is linearly dependent in the coordinate space of dimension n+1.

Proof The existence of a non-trivial scalar k-tuple solving equations 2.5 and 2.6 implies that

(2.7)

and vice versa.

Corollary 2.1.2 Systems containing at least n+2 vectors are affinely dependent.

Proposition 2.1.3 The system 2.4 is affinely independent if and only if for any index i the position vectors

(2.8)

are linearly independent.

Proof Observe that linear combinations of the position vectors 2.8 mean combinations of 2.4 such that the sum of the coefficients is zero and vice versa.

Remark The affine dependence means that we have a non-trivial polygonal chain with sides parallel to the position vectors from one of the elements to the others in the given system (lasso).

Corollary 2.1.4 The system

(2.9)

is affinely independent if and only if the affine hull is of dimension k.

Corollary 2.1.5 Suppose that the system 2.9 is affinely independent. Then any point p of the affine hull has a unique representation as an affine combination of the elements 2.9. The coefficients in this combination are called the affine coordinates of the point p with respect to 2.9.

2.2 Carathéodory's theorem

The following theorem belongs to the foundations of the theory of convex sets. It was first proved by Constantin Carathéodory in 1907. In section 1.3 of the previous chapter the convex hull conv H was defined as the collection of convex combinations of the elements from H but we have no any restriction on the number of points of H required to make the combination. Carathéodory's theorem gives a precise answer to the question how to generate the convex hull without unnecessarily repetitions: the number of points of H in the convex combination never has to be more than n+1.

Figure 22: Constantin Carathéodory, 1873-1950.

Theorem 2.2.1 (Carathéodory, Constantin). The convex hull is just the set of convex combinations of affinely independent elements.

Proof Let

be a convex combination and suppose that the system v(1), ..., v(k) is affinely dependent. To reduce the number of elements in the convex combination consider the set

(2.10)

in the coordinate space of dimension k. The point

is one of its elements. By the affine dependence there exists a non-trivial solution of the following system of equations:

and

Therefore

is a non-zero vector parallel to the hyperplane (the affin hull) of 2.10. Let us start from λ into the direction represented by μ and go as far as we leave 2.10. In terms of the linear algebra choose a non-negative scalar t such that

is on the relative boundary[3] of 2.10.

Figure 23: Carathéodory's theorem.

This element involves new coefficients for a convex combination of vectors v(1), ..., v(k) and one of the new coefficients must be zero because of the boundary-condition. Moreover

The process can be repeated as far as the system of vectors in the convex combination is affinely dependent. ▮

Theorem 2.2.2 The convex hull of a compact set is compact.

Proof Using Carathéodory theorem the convex hull of the set H in the coordinate space of dimension n is just the image of the set

under the mapping

where

The Cartesian product of compact sets is obviously compact. So is the convex hull because of the continuity of the mapping Φ. ▮

Definition The convex hull of an affinely independent system of vectors 2.9 is called a simplex of dimension k. The elements of 2.9 are the vertices of the simplex.

It can be easily seen that each point p from the convex hull of a simplex has a unique representation as a convex combination of the vertices. The coefficients in this combination are called the barycentric coordinates of the point p. The element

(2.11)

is called the centroid of the simplex.

Corollary 2.2.3 A point p is in conv H if and only if p is in a simplex with vertices from H.

Corollary 2.2.4 The convex hull of a set H in the plane can be considered as the union of convex hulls of at most three points belonging to H. The convex hull of a set H in the space of dimension three can be considered as the union of convex hulls of at most four points belonging to H.

2.3 The colorful Carathéodory's theorem

In this section we present a generalization of Carathéodory's theorem due to Imre Bárány [4]. The result was published in 1982 together with further generalizations and applications (see e.g. the cone-version of Carathéodory's theorem and applications to convex functions).

Theorem 2.3.1 Let

be non-empty subsets in the coordinate space of dimension n and suppose that

Then there exists elements

(2.12)

such that p is in the convex hull of

Proof Since p is a common element of the convex hulls of the subsets we can suppose, by the classical version of Carathéodory's theorem, that each subset is finite (we can substitute the subset with one of its simplices containing the element p if necessary). Consider the convex hulls of the form

(2.13)

as each argument runs through the (finitely many) elements of the corresponding subset. Since there are only finitely many convex hulls of type 2.13 we can suppose that

is as close to p as possible. If p is in C then the proof is finished. Suppose that p is not in C and consider a point q in C as close to p as possible. Let D be the open ball centered at p with radius r=d(p,q). The interior of D and C is obviously disjoint; see figure 24. Consider now the tangent hyperplane to the ball at q. Because of theconvexity C and the open half-space containing p must be also disjoint.

Figure 24: Separation: the proof of 3.1.

In what follows we claim that q can be expressed as a convex combination of at most n elements from v(1), ..., v(n+1). If it is an affinely dependent system then the statement is obvious (see Carathéodory's theorem for the reduction of the number of members in the convex combination). Otherwise q can not be in the interior of C because it is the closest point to p from C. Therefore at least one of the elements from v(1), ..., v(n+1) must have a zero coefficient in the convex combination presenting q. Suppose that the first element is missing. Then it can be substituted with any element of the first subset in such a way that the distance between p and the modified convex hull C' is the same as the (minimal) distance between p and C. The last question is how to substitute this element to present a contradiction. Because p is especially in the convex hull of the first subset we can find an element

in the same open half-space as p. Such a substitution obviously decreases the distance between p and C' as figure 24 shows. This contradicts to the minimality condition. ▮

Remark Image that the points of H(i) have color i. The theorem asserts the existence of the colorful covering simplex

for the point p. The ''colorful'' means ''containing all colors'' [5]. If

then we have the classical version of Carathéodory's theorem.

2.4 Excercises

Excercise 2.4.1 Check the affine dependence/independence of the system

Excercise 2.4.2 Prove or disprove the following statements:

• Linearly independent systems are affinely independent.

• Affinely independent systems are linearly independent.

• Linearly dependent systems are affinely dependent.

• Affinely dependent systems are linearly dependent.

Excercise 2.4.3 Check the affine dependence/independence of the system

Excercise 2.4.4 Check the affine dependence/independence of the following systems of vectors.

Excercise 2.4.5 Find the affine coordinates of

in the coordinate plane with respect to

(2.14)

Using affine coordinates how to characterize points in the interior, points on the boundary or points outside of conv 2.14.

Excercise 2.4.6 Prove that

are affinely independent and find the affine coordinates of the origin in the coordinate space of dimension four.

Excercise 2.4.7 Consider the vector

where

Use the procedure in the proof of Carathéodory's theorem 2.2.1 to reduce the number of the members in the convex combination as far as possible.

Excercise 2.4.8 Consider the vector

where

Use the procedure in the proof of Carathéodory's theorem 2.2.1 to reduce the number of the members in the convex combination as far as possible.

Excercise 2.4.9 Consider the vector

where

Use the procedure in the proof of Carathéodory's theorem 2.2.1 to reduce the number of the members in the convex combination as far as possible.

Excercise 2.4.10 Consider the vector

where

Use the procedure in the proof of Carathéodory's theorem 2.2.1 to reduce the number of the members in the convex combination as far as possible.

3. fejezet - Helly's theorem

Helly's theorem gives a criteria to provide the existence of common elements in each member of a family of convex sets in the space. The one-dimensional version is that if we have a finite collection of intervals and any twoof them have a common point then all of them have a common point. For an alternative formulation image that each interval represents the time that a guest spends at a party. The existence of the common point of each pair of the intervals corresponds to the moment when two guests welcome to each other. It is clear that if x denotes the guest who is the first to leave the party at the moment t(0) then there is no any guest who arrives after t(0) otherwise such a guest can not welcome to x. On the other hand there is no any guest to leave the party before t(0) because x is the first. Therefore t(0) is a moment when all the guests are at the party at.

3.1 Radon's lemma

Lemma 3.1.1 (Radon, Johann). Let D be the set consisting of the elements

in the coordinate space of dimension n. If k is at least n+2 then D can be partitioned into two disjoint subsets such that their convex hulls intersect each other, i.e.

but

Proof Since k is at least n+2 the elements in D are affinely dependent, i.e. we have a non-trivial k-tuple of scalar multipliers such that

(3.1)

and λ(1)+ ...+λ(k)=0. Because the sum of the coefficients is zero there must be numbers with different signs among them. For the sake of definiteness suppose that

Let

Then, by 3.1

and the element v is contained in the convex hulls of both

as was to be proved. ▮

Figure 25: Johann Radon, 1887-1956.

3.2 Tverberg's theorem

In this section we discuss a generalization of Radon's lemma. The theorem was first proved in 1966 by Helge Arnulf Tverberg. We present a proof due to Karanbir Sarkaria (Combinatorics and more, http://gilkalai.wordpress.com) based on the colorful Carathéodory's theorem 3.1.

Theorem 3.2.1 Let D be the set consisting of the elements

in the coordinate space of dimension n. If m is at least

then D can be partitioned into r pairwise disjoint subsets such that their convex hulls intersect each other.

Proof Without loss of generality we can suppose that

Consider the vectors v(1), ..., v(k) as the elements in the coordinate space of dimension n+1 by adding a new coordinate to each vector in such a way that the sum of the coordinates is just one. Let us choose a collection of vectors w(1), ..., w(r) in the coordinate space of dimension r - 1 such that

(3.2)

is the only linear relation among them up to a non-zero multiplicative constant and define the tensorial product

as a matrix

It can be considered as an element in the coordinate space of dimension d=(n+1)(r - 1). Let

It can be easily seen that

and, consequently, the origin is just the center lying in the convex hulls of H(i)'s. Since m=d+1 the colorful Charathéodory theorem says that

(3.3)

where h(k) is in H(k) for any index k. The partition is realized in the following way:

We can obviously write equation 3.3 into the form

(3.4)

If we consider equation 3.4 as a system of equations for the rows of the matrices we have, for example, that

(3.5)

In a similar way (for the second row)

(3.6)

and so on. This means by equation 3.2 that

(3.7)

for any indices j=1, ..., n+1. Therefore

(3.8)

Since the sums of the coordinates of the elements v(1), ..., v(n+1) are one we have that[4]

On the other hand

and, consequently, λ=1/r. Finally

(3.9)

where (for example)

Therefore rv is in all the convex hulls conv D(1), conv D(2), ..., conv D(r) as was to be proved. ▮

Excercise 3.2.2 Use the technic of Sarkaria's proof to find the partition of the elements

in the coordinate plane into three disjoint subsets.

Figure 26: A partition into three disjoint subsets.

Hint. First of all note that n=2, r=3 and m=7. Consider the vectors v(1), ..., v(7) as the elements in the coordinate space of dimension 3 by adding a new coordinate to each vector in such a way that the sum of the coordinates is just one:

On the other hand let

We have that

are the elements in H(1). In a similar way

are the elements in H(2), ..., H(7), respectively. Observe that

and the partition is

3.3 Helly's theorem

Theorem 3.3.1 (E. Helly, 1913). Let B be the collection consisting of convex subsets

in the coordinate space of dimension n. If k is at least n+1 and every subfamily of n+1 sets in B has a non-empty intersection then the family of all sets in B has a non-empty intersection.

Figure 27: Eduard Helly, 1884-1943.

Proof The proof is based on a simple induction. If k=n+1 then the statement is trivial. Suppose that it is true in case of k > n+1 and consider the family consisting of convex subsets

(3.10)

We can apply the inductive hypothesis to the reduced family

where the hat - operator deletes its argument. The reduced family obviously heritages the property of non-empty intersections for its subfamilies because they are subfamilies of the extended collection 3.10 too. Then we have an element

In a similar way

Let D be the set consisting of the elements v(1), ..., v(k+1) and use Radon's lemma 3.1.1 to give a partition D=D(1) U D(2) such that the convex hulls of the sets D(1) and D(2) have a non-empty intersection. For the sake of simplicity suppose that

if v is a common element of the convex hulls then we have that

and

Therefore v is in the intersection of the sets 3.10 as was to be proved. ▮

Figure 28: Helly's theorem 3.3.1.

The figure illustrates that the sets in Helly's theorem must all be convex. On the other hand if we omit the requirement of finiteness the theorem becomes false as we can see for example in case of the family consisting of the convex sets

in the coordinate plane with

The Helly number n+1 cannot be reduced in general: every two sides of a triangle have a point in common, but all the sides do not. The following result due to Victor Klee [36] involves some information about the size of the intersection.

Theorem 3.3.2 (Klee, Victor) Let B be the collection consisting of convex subsets

in the coordinate space of dimension n and suppose that K is a non-empty subset. If k is at least n+1 and for every subfamily of n+1 sets in B there exists a translate of K contained in all n+1 of them then there exists a translate of K contained in all the members of B.

Proof Consider a new collection A of subsets

(3.11)

where i=1, ..., k. We are going to prove that A satisfies the conditions of the original Helly's theorem 3.3.1. For the sake of definiteness consider two points p and q belonging to the first member A(1) of the family 3.11:

(3.12)

Let λ be a real number between 0 and 1. If v is an element from the set

then it can be written into the form

for some w in K. By our hypothesis 3.12

together with their convex combination v. Therefore

(condition of the convexity). Since for every subfamily of n+1 sets in B there exists a translate of K contained in all n+1 of them, every subfamily of n+1 sets in A has a non-empty intersection. Helly's theorem implies that the family of all sets in A has a non-empty intersection. If p* is one of the common elements then p*+K is contained in all the members of B. ▮

The followingtheorem gives a Helly-type answer to the question how to cover subsets in the space by translates of a given convex set. It will be applied in section 4.2.

Theorem 3.3.3 (Klee, Victor) Let B be the collection consisting of convex subsets

in the coordinate space of dimension n and suppose that K is a non-empty convex subset. If k is at least n+1 and for every subfamily of n+1 sets in B there exists a translate of K containing all n+1 of them then there exists a translate of K containing all the members of B.

Proof Consider a new collection A of subsets

(3.13)

where i=1, ..., k. We are going to prove that A satisfies the conditions of the original Helly's theorem 3.3.1. For the sake of definiteness consider two points p and q belonging to the first member A(1) of the family 3.13:

(3.14)

If b(1) is in B(1) then, by our hypothesis 3.14,

for some elements w and z in K. Let λ be a real number between 0 and 1. Then

and the convex combination of w and z is in K because of the convexity. Therefore

and

(condition of the convexity). Since for every subfamily of n+1 sets in B there exists a translate of K containing all n+1 of them, every subfamily of n+1 sets in A has a non-empty intersection. Helly's theorem implies that the family of all sets in A has a non-empty intersection. If p* is one of the common elements then p*+K contains all the members of B. ▮

In what follows we present some results to illustrate typical applications of Helly's theorem.

Corollary 3.3.4 Let F be a finite set of points in the coordinate plane. If each triangle formed by the points of F can be covered by a disk with radius r, then F can be covered by a disk with radius r.

Proof Let B be the collection consisting of the closed disks

(3.15)

around the points in F with radius r. Because each triangle formed by the points in F can be covered by a disk with radius r we have a point (the center of the covering disk) having distances from the vertices of the triangle less than or equal to r. Therefore it is a common point of three corresponding disks from the collection B. Using Helly's theorem it follows thatthe family 3.15 has a non-empty intersection. If p* is one of the common elements of B(1), ..., B(k) then the disk around p* with radius r obviously covers the elements of F. ▮

Corollary 3.3.5 (H. Jung). Let F be a finite set of points in the coordinate plane with diameter

Then F can be covered by a disk with radius r.

Proof Because of the previous corollary it is enough to prove that each triangle formed by the points in F can be covered by a disk with radius r. If the points are collinear (degenerate triangles) or they form an obtuse/right triangle then covering disk(s) with radius d/2 can be found. Therefore we discuss only the case of acute triangles.It can be easily seen that there is an angle γ having at least π/3 radian in the measure. Then the radius R of the circumscribed circle can be estimated as

because the sine function is strictly increasing in the first quadrant. ▮

Remark Note that the upper bound in Jung's theorem is attained in case of a regular triangle.

Corollary 3.3.6 Let F be a finite set containing m points in the coordinate plane. If d is the diameter and

is the minimal distance among the points of F then

(3.16)

i.e. the ratio between the longest and the shortest distances can be estimated from below by the square root of the number of elements.

Proof Consider the disks D(1), ..., D(m) around the points of F with radius δ/2. Since the interiors of the disks are pairwise disjoint the area of their union is

(3.17)

Using Jung's theorem 3.3.5 the union of D(1), ..., D(m) can be covered by a disk with radius

From the last inequality we have 3.16 immediately. ▮

Corollary 3.3.7 The minimal distance tends to zero under increasing the number of points in a bounded box.

3.4 Excercises

Excercise 3.4.1 Let D be the set consisting of the elements

in the coordinate plane. Find a Radon's partition for D.

Excercise 3.4.2 Let D be the set consisting of the elements

in the coordinate plane. Find a Radon's partition for D.

Excercise 3.4.3 Let D be the set consisting of the elements

in the coordinate space of dimension 3. Find a Radon's partition for D.

Excercise 3.4.4 Prove the one-dimensional version of Helly's theorem.

Hint. Use that real numbers form an Archimedean complete totally ordered field.

Excercise 3.4.5 Let B be the collection consisting of convex subsets

in the coordinate space of dimension n. Prove that if k is at least n and every subfamily of n sets in B has a non-empty intersection then the family of all sets in B has a common transversal parallel to any given 1-dimensional affine subspace/line in the space.

Hint. Let a 1-dimensional affine subspace be given and consider its orthogonal complement of dimension n - 1. Use Helly's original theorem3.3.1 to find a common point for the projected sets.

Excercise 3.4.6 How to generalize Corollary 3.3.4 to the coordinate space of dimension n?

Excercise 3.4.7 Why Corollary 3.3.4 is a special case of Klee's second theorem?

Excercise 3.4.8 How to generalize Jung's theorem 3.3.5 to the coordinate space of dimension three?

Excercise 3.4.9 How to generalize inequality 3.16 to the coordinate space of dimension three?

4. fejezet - Generalizations and Applications

Helly's theorem can be extended to infinite collections of convex sets but not without some additional restrictions as we shall see.

4.1 Helly's theorem: generalizations and applications

Theorem 4.1.1 (The countable version) Let B be the collection consisting of the sequence

of compact convex sets in the coordinate space of dimension n. If every subfamily of n+1 sets in B has a non-empty intersection then the family of all sets in B has a non-empty intersection.

Proof Using the original version 3.3.1 of Helly's theorem we can produce a sequence

Because of the compactness we can choose a convergent subsequence with the limit point p*. It is obviously a common point in all the members in B because if the index of the elements in the subsequence is large enough then the sequence runs in the corresponding compact set from B. ▮

Theorem 4.1.2 (The general version). Let B be the family of compact convex sets in the coordinate space of dimension n and suppose that B contains at least n+1 members. If every subfamily of n+1 sets in B has a non-empty intersection then the family of all sets in B has a non-empty intersection.

Proof Suppose, in contrary, that the intersection of the members in B is the empty-set. Then the union of their complement is just an open cover of the space. By Lindelöf theorem 1.2.1 we can choose acountable subcover and, consequently, the intersection of the corresponding members from B must be also empty. This contradicts to the countable version 4.1.1. ▮

In what follows we adopt the results in chapter 3 to the general version 4.1.2 of Helly's theorem together with some new applications.

Theorem 4.1.3 (Klee, Victor) Let B be the family of compact convex sets in the coordinate space of dimension n and suppose that Bcontains at least n+1 member. If K is a non-empty subset and for every subfamily of n+1 sets in B there exists a translate of K contained in all n+1 of them then there exists a translate of K contained in all the members of B.

Proof Consider a new collection A of subsets

(4.1)

where γ runs through the index set Γ. We are going to prove that A satisfies the conditions in the general version 4.1.2 of Helly's theorem. For the sake of definiteness consider two points p and q belonging to the member A(γ) of the family 4.1:

(4.2)

Let λ be a real number between 0 and 1. If v is an element from the set

then it can be written into the form

for some w in K. By our hypothesis 4.2

together with their convex combination v. Therefore

(condition of the convexity). On the other hand suppose that the sequence p(m) in A(γ) tends to the limit p. Then for any k in K

because p(m)+k is in B(γ) and B(γ) is compact (especially closed). This means that p+K is a subset in B(γ), i.e. p is in A(γ) (condition of closedness). Finally K is bounded because compact (especially bounded) subsets contain translates of K. So is each member of A. Since for every subfamily of n+1 sets in B there exists a translate of K contained in all n+1 of them, every subfamily of n+1sets in A has a non-empty intersection. The general version 4.1.2 of Helly's theorem implies that the family of all sets in A has a non-empty intersection. If p* is one of the common elements then p*+K is contained in all the members of B. ▮

Theorem 4.1.4 (Klee, Victor) Let B be the family of compact convex sets in the coordinate space of dimension n and suppose that B contains at least n+1 member. If K is a non-empty compact convex set and for every subfamily of n+1 sets in B there exists a translate of K containing all n+1 of them then there exists a translate of K containing all the members of B.

Proof Consider a new collection A of subsets

(4.3)

where γ runs through the index set Γ. We are going to prove that A satisfies the conditions in the general version 4.1.2 of Helly's theorem. For the sake of definiteness consider two points p and q belonging to the member A(γ) of the family 4.3:

(4.4)

If b(γ) is in B(γ) then, by our hypothesis 4.4,

for some elements w and z in K. Let λ be a real number between 0 and 1. Then

and the convex combination of w and z is in K because of the convexity. Therefore

and

(condition of the convexity). On the other hand suppose that the sequence p(m) in A(γ) tends to the limit p. By the definition of A(γ) any element b(γ) in B(γ) can be written into the form

for a sequence v(m) of elements in K. Since K is compact (especially closed)

and, consequently,

(condition of closedness). Finally K is bounded and its translates with elements from A(γ) must cover a compact (especially bounded) subset B(γ). This means that A(γ) must be bounded. Since for every subfamily of n+1 sets in B there exists a translate of K containing all n+1 of them, every subfamily of n+1 sets in A has a non-empty intersection. The general version 4.1.2 of Helly's theorem implies that the familyof all sets in A has a non-empty intersection. If p* is one of the common elements then p*+K contains all the members of B. ▮

Finally we present a Helly-type theorem without any condition of compactness for the member of the family of sets. In order to motivate the result discuss the following outline how to prove the general version of Helly's theorem:

(i) conditions (compactness, convexity, non-empty intersection of every subfamily containing n+1 members) --> countable version of Helly's theorem,

(ii indirect argumentation involving Lindelöf's theorem --> contradiction to the countable version.

In order to avoid compactness in the conditions the following result use the countable version directly as a requirement.

Theorem 4.1.5 Let B be the family of closed subsets in the coordinate space of dimension n and suppose that every countable subfamily of B has a non-empty intersection. Then the family of all the members in B has anon-empty intersection.

Closedness can be substituted with convexity as well.

Theorem 4.1.6 (Klee, Victor) Let B be the family of convex subsets in the coordinate space of dimension n and suppose that every countable subfamily of B has a non-empty intersection. Then the family of all the members in B has a non-empty intersection.

For the proof of a more general theorem see chapter 6, see also [35].

Theorem 4.1.7 Let B be the family of closed convex sets in the coordinate space of dimension n and suppose that B contains at least n+1 members. If one of them is compact and every subfamily of n+1 sets in B has a non-empty intersection then the family of all sets in B has a non-empty intersection.

Proof Let K be the distinguished compact element of the family and apply the general version to the collection

All the new sets are compact and every subfamily of n+1 sets in the new collection has a non-empty intersection because of the finite version of Helly's theorem. Therefore the general version 4.1.2 implies that all sets in B has a non-empty intersection.

4.2 Universal covers and approximately central symmetry

Definition A compact subset K in the coordinate plane is a universal cover if any compact convex subset having diameterone can be covered by a congruent copy of K.

The problem of finding the smallest universal cover of a given class of objects is very natural and important. Here we illustrate only the cases of disks (as an excercise) and squares because they are directly in the competence of Helly's theorem.

Definition Consider an equilateral triangle in the coordinate plane. The Reuleaux triangle is formed by three circular arcs lyingon the sides of the triangle with centers running through the vertices.

Figure 29: The Reuleaux triangle.

The problem we are going to discuss here is how a square can be rotated around the Reuleaux triangle?

Figure 30: Tangent lines.

Let

be the vertices of the regular triangle (the common length of the sides is 2) and consider the one-parameter family

(4.5)

of lines, where c(t)=sin t - 2 is given in such a way that the line at t is tangent to the arc AC of the circle centered at B with radius 2. The one-parameter family of lines parallel to 4.5 through the point B is

In a similar way

(4.6)

is the one-parameter family of lines, where

is given in such a way that the line at t is tangent to the arc AB of the circle centered at C with radius 2. Lines 4.5 and 4.6 give adjacent sides of the circumscribed square around the Reuleaux triangle when the parameter is between 60 and 90; see figure 30. The corresponding vertex[5] moves along the path K(t) with coordinate functions

The opposite vertex moves along M(t) with coordinate functions

Finally (the missing vertices)

and the motion of the center can be described as

with coordinate functions

where t is between 60 and 90 degree's (a routine calculation shows that T(60) and T(90) can be seen under the angle of measure 120 degree from the center of the triangle). If R is the rotation about the center of the triangle with magnitude +120 then the center of the circumscribed squares moves along the path

the figure 31 shows the curve T(t) with a full period t=0 ... 360. An animation can be available at zeus.nyf.hu/ kovacsz/Csaba.

Figure 31: The curve T(t) with a full period: the limacon.

Remark Conversely the Reuleaux triangle can be rotated through 360 degree inside a square although the center of the rotation moves along an excentric path.

Theorem 4.2.1 The smallest universal cover among squaresin the coordinate plane is the square having sides of length one.

Proof Let K be a square having sides of lenght one and consider a compact convex set F with diameter 1 in the coordinate plane. In the sense of theorem 4.1.4 it is enough to prove that for any three points in F there exists a translate of K covering them. Let p(1), p(2) and p(3) be three points in F. Since its diameter is one there exists a Reuleaux triangle constructed from an equilateral triangle with sides of length one such that it contains p(1), p(2) and p(3). But such a shape can be rotated through 360 degree in a square of side 1. This means that there exists a translate of K covering the Reuleaux triangle (together with p(1), p(2) and p(3)) independently of its orientation. Therefore 4.1.4 says that there exists a translate of K covering F. To cover a disk of diameter one we obviously need a square having sides of length at least one.

Theorem 4.2.2 Let K be a two-dimensional compact convex subset in the plane. There exists a point in the interior of K such that it belongs to the middle part of the trisection of any chord passing through this point.

Proof Consider a triangle Δ formed by the boundary points of K and use central similarities from the vertices of the triangle with ratio 2/3. The barycenter of Δ is a common point of the images of K under the three similarities. Using the general version 4.1.2 of Helly's theorem there exists a point p* in the intersection of the images of K under the similarities as the center runs through the boundary of K. If a chord contains this common point then we can use the central similarities relative to the endpoints of such a chord with ratio 2/3 to prove that p* must be in the middle part of the trisection.

4.2.1 The Brunn-Minkowski inequality

The most famous problem related to universal covers was posed by H. Lebesgue: what is the minimum area that a universal cover in the coordinate plane can have? This is related to a whole class of extremum problems wherein one quantity is to be minimized or maximized subject to certain restraining conditions. The best known of all the extremum problems is the classical isoperimetric problem; which simple closed curve of given perimeter encloses the greatest area? It is not hard to prove that among all rectangles of perimeter 1 the square has the greatest area. Likewise among triangles of perimeter 1 the equilateral triangle has the greatest area. In general the answer is again the most symmetrical shape, which in this case is the circle. Rigorous proofs are hard to find. In what follows we present a theoretical way of the solution via the Brunn-Minkowski inequality for convex bodies in the space. It is not at all unreasonable to expect that a solution to the isoperimetric problem is a convex body. If we accept, for the moment, an intuitive notion of the area and perimeter of a non-convex set then the convex hull of this set has expectedly a shorter perimeter and a larger area.

Definition Convex bodies mean compact convex sets with non-empty interiors in the coordinate space.

Theorem 4.2.3 (Brunn-Minkowski inequality) For convex bodies in the coordinate space of dimension n we have

(4.7)

where V refers to the volume of the bodies.

Proof In what follows we sketch the steps of the proof due to W. Blaschke; for more details and historical remarks see [27]. It is based on the so-called Steiner symmetrization process. Let u be a unit vector in the space. The Steiner symmetral S(u)K of K in the direction u is a convex body obtained from K by sliding eachof its chords parallel to u so that they are bisected by its orthogonal complement. By Cavaliéri's principle K and S(u)K have the same area. On the other hand the Steiner symmetral of the sum K+L contains the sum of the Steiner symmetrals in any given direction. Therefore

(4.8)

Let B be the unit ball centered at the origin. One can also prove that there is a sequence of directions u(m) such that the iteration

tends to the Euclidean ball r(K)B with respect to the Hausdorff metric. It is clear that the constant r(K) is just the nth root of the ratio between the volumes of K and B. Since r(K)B+r(L)B=(r(K)+r(L))B we have that

(4.9)

which is just the Brunn-Minkowski inequality 4.7 as was to be proved.

Minkowski's definition of the surface area A(K) of a convex body is

(4.10)

Excercise 4.2.4 Compute the surface area of a square in the plane by Minkowski's definition.

Remark Let K be a convex body in the plane bounded by a smooth curve c. Since tangent lines of c are working as supporting hyperplanes it follows that c+ε n is the parameterization of the boundary of K+εB, where n is the outer pointing unit normal vector field along c. Under the choice of the arclenght parameter into the counterclockwise direction

see section 11.2 for the elements of differential geometry. We have

where P is the arclength of c. Therefore

Since n and c' are orthogonal unit vectors det( n, c')=1. On the other hand

Using the rule of partial integration and the periodocity of the curve c it follows that

because of the arclenght parameter.

Excercise 4.2.5 Prove that the ratio between the surface area and the volume of the unit ball is just the dimension of the space.

The last step of the derivation of the isoperimetric inequality for convex bodies is

which implies by the ratio A(B) : V(B)=n, that

(4.11)

Remark Equality holds in the isoperimetric inequality 4.11 if and only if K is a ball. For the Brunn-Minkowski inequality and its relatives see [27], see also [52]. A nice presentation of a differential geometric proof in the plane can be found in [51].

4.3 A sandwich theorem

Theorem 4.3.1 Let B be a family of parallel compact segments with different supporting lines in the coordinateplane such that any three segments have a common transversal line. Then there exists a line transversal to all the members of B.

Proof Without loss of generality we can suppose that all the segments parallel to the second coordinate axis labelled by y. Consider such a segment with endpoints (a,r) and (a,s), where r < s and let

(4.12)

be a line intersecting this segment. Then the common point has the second coordinate ma+b. Therefore

showing that

(4.13)

Let us define the parallel lines

(4.14)

corresponding to the endpoints of the segment and consider the point p with coordinates (m,b) corresponding to the line 4.12. Inequalities 4.13 shows that p is an element of the band bounded by the parallel lines 4.14. Therefore we can reformulate our condition in the following way: we have a collection of bands such that any three bands have a common point. The goal is to prove that all of them have a common point. Since the segments have different supporting lines it is easy to create a compact convex set K in the family we are interested in. Actually the intersection of finitely many not parallel bands is a convex polygon as the intersection of finitely many closed half-planes, see chapter 9. Then the corresponding version 4.1.7 of Helly's theorem implies the existence of the common point of the bandsand we also have a line intersecting all segments in B.

Remark Theorem 4.3.1 plays an important role in the theory of approximation of continuous functions with polynomials. In what follows we show another application resulting in a sandwich theorem [44]. The result presents necessary and sufficient conditions under which the graphs of two functions can be separated by a straight line (functions having lines as graphs are called affine functions).

Theorem 4.3.2 (K. Nikodem and Sz. Wasowicz) Let f and g be real functions defined on a real interval I. There exists an affine function h satisfying the inequalities

if and only if

(4.15)

and

(4.16)

hold for any x, y from I and λ between 0 and 1.

Proof Since affine functions preserve the affine (especially convex) combinations of the elements it is obvious that if an affine function h is between f and g then conditions 4.15 and 4.16 are also satisfied for any x, y from I and λ between 0 and 1.

Figure 32: The proof of the sandwich theorem.

To prove the converse of the statement first of all note that f(x) is less or equal than g(x). It can be easily seen by substitution λ=1. Consider now the set of segments with endpoints (x, f(x)) and (x, g(x)) as x runs through the elements of the interval I. These are parallel compact segments with different supporting lines in the coordinate plane. To finish the proof we are going toshow that this collection of segments satisfies the condition of the previous theorem. Let x(1) < x(2) < x(3) be three different points in I and consider the coefficient λ such that x(2)=λ x(1)+(1 - λ)x(3). Using the notations

condition 4.15 says that (x(2),y(2)) is under the line of (x(1),z(1)) and (x(3),z(3)). At the same time, by condition 4.16, (x(2),z(2)) is above the line of (x(1),y(1)) and (x(3),y(3)). These conditions obviously guarantee the existence of a common transversal to the segments at x(1), x(2) and x(3), respectively. Finally the previous theorem shows the existence of a common transversal to all the segments as well. This is just the graphof an affine function h between f and g as was to be proved.

Corollary 4.3.3 If a convex function majorizes a concave one then there exists an affine function between them.

Remark Necessary and sufficient conditions for the existence of separation by members of a given linear interpolation family can be found in [46]: the proof is also based on Helly's theorem.

4.4 Excercises

Excercise 4.4.1 Prove the one-dimensional version of Helly's theorem for an arbitrary collection of compact intervals.

Hint. Use that real numbers form an Archimedean complete totally ordered field.

Excercise 4.4.2 Let B be the family of compact convex sets in the coordinate space of dimension n and suppose that B contains at least n members. Prove that if every subfamily of n sets in B has a non-empty intersection then the familyof all sets in B has a common transversal parallel to any given 1-dimensional affine subspace/line in the space.

Hint. Let an 1-dimensional affine subspace be given and consider its orthogonal complement of dimension n - 1. Use the general version 4.1.2 of Helly's theorem to find a common point for the projected sets.

Excercise 4.4.3 Prove theorem 4.1.5.

Excercise 4.4.4 Prove the general version of Jung's theorem 4.3.5 to find the smallest radius for a universal covering disk in the plane.

Excercise 4.4.5 Calculate the perimeter and the area of a Reuleaux triangle in terms of the side of the equilateral triangle.

Excercise 4.4.6 Find the measure of the interior angle at the corners of the Reuleaux triangle.

Excercise 4.4.7 Prove that Reuleaux triangles are complete in the sense that no points from their complements can be added to them without increasing the diameter.

Excercise 4.4.8 How to generalize theorem 4.2.2 to the coordinate space of dimension three?

5. fejezet - Krasnosselsky's art gallery theorem

5.1 Krasnosselsky's art gallery theorem

One of the interesting applications of the general version 4.1.2 of Helly's theorem is the art gallery theorem of M. A. Krasnosselsky (1946). The theorem belongs to the basis of art gallery geometry. It formulates acriteria of viewing all the paintings in the gallery without changing position (this is the case of n=2).

Definition Let D be a non-empty subset in the coordinate space of dimension n and consider the points p and q in D. The point q is said to be visible[6] from p if D contains the segment s(p,q). The set D is star-shaped relative to a point p in D if all the points of D are visible from p. The kernel of D is the collection of those points in D with respect to which D is star-shaped.

Theorem 5.1.1 (M. A. Krasnosselsky) Let D be a non-empty compact subset in the coordinate space of dimension n and suppose that D contains at least

points. If for every n+1 points in D there exists a point in D from which they are visible then there exists a point in D from which all the points of D are visible, i.e. D is star-shaped.

Proof Let p be a point in D and consider the set of points in D which are visible from p:

(5.1)

First of all we prove that the family of conv B(p)'s (as p runs through the points of D) satisfies the conditions in the general version 4.1.2 of Helly's theorem. To prove that they are compact sets it is enough to check that they are closed because

where conv D is compact in the sense of theorem 2.2.2. Let q* be the limit of the convergent sequence q(i) from conv B(p). Using Carathéodory's theorem 2.2.1 for each index i we can write that

(5.2)

where the right hand side involves a convex combination of elements in B(p). The coefficients obviously form bounded sequences and the sequences

(5.3)

are also bounded because they run in the compact set D. Therefore we can choose uniformly labelled convergent subsequences in a successive way. If

are their limits then

where the right hand side involves a convex combination of elements from B(p). Indeed,

are trivial because the members of the corresponding sequences also satisfy these relations. We should also check that the elements v*(1), ..., v*(n+1) are in B(p). Suppose in contrary that v*(1) is not in B(p) which means that the segment s(v*(1), p) contains an element q in the complement of D. But D is compact (especially closed) and, consequently, there is an open ball around q which is disjoint from D.This ball hides the point p from the elements of a neighbourhood around the endpoint v*(1) which contradicts to the fact that v*(1) is a limit of elements which are visible from p. Therefore q* is in conv B(p) showing that it is a closed subset. Moreover, as a closed subset of conv D, the convex hull of B(p) is also compact. Since for every n+1 points in D there exists a point in D from which they are visible, the general version 4.1.2 of Helly's theorem implies the existence of a common point of the convex hulls of sets in 5.1. Let u be one of the common elements, i.e. u is in conv B(p) for any p in D. To complete the proof we should see that u is also in the intersection of sets in 5.1 (without conv - operator) as p runs through the points of D. Suppose, in contrary, that u is not in B(p) (for some p), i.e. the segment s(p,u) contains an element v in the complement of D. The distance

between v and the compact set D must be strictly positive. Let v(0) be the closest point of D to v along the segment s(p,v) and let z in s(v(0),v) be such a point that

(5.4)

Finally, let z(0) and p(0) be the points where the distance d(s(z,v), D) is attained at:

Figure 33: The proof of Krasnosselsky's theorem.

Since p(0) is the closest point of D to z(0) we have that

because of 5.4. This means that z(0) and v are different. On the other hand a simple nearest-point-type argumentation (see e.g. theorem 3.1 or section 7.1) shows that the hyperplane H(0) perpendicular to the segment s(z(0),p(0)) at p(0) separates z(0) and the points in B(p(0)) (the set of points in D which are visible from p(0)). Therefore the convex hull of B(p(0)) (together with the point u) and z(0) are alsoseparated. In terms of the internal angles of the triangle spanned by p(0), z(0) and u

Since z(0) and v are different we have a point on

which is closer to p(0) than z(0). This contradicts to the choice of z(0).

▮

5.2 Excercises

Excercise 5.2.1 Prove that the kernel of D is convex.

Excercise 5.2.2 Find the kernels of the following shapes in the plane.

Excercise 5.2.3 Prove that the points

in the proof of Krasnosselsky's theorem is not collinear.

Hint. In case of collinear points we have that p(0)=v(0) and z=z(0). Therefore H(0) separates the convex hull of B(p(0)) and u which is obviously a contradiction.

Figure 34: Kernels of sets in the plane.

Figure 35: The kernel as a singleton.

6. fejezet - Intersections of star-shaped sets

A recent trend in convex geometry is to investigate intersections of sets under a weaker condition than convexity. In 2001 N. A. Bobylev [9] provided a star-shaped set analogue of Helly's theorem. Especially Bobylev proved that if we have a family B of compact sets in the coordinate space of dimension n and every n+1 (not necessarily different) members of B have a star-shaped intersection then the intersection of all elements in B is star-shaped. The star- shaped set analogue of Klee's theorem 4.1.6 is true as well. In fact the result due to Marilyn Breen [15] states that the associated intersection is non-empty, star-shaped and its kernel is at least k-dimensional for an appropriate choice of k between 0 and n.

6.1 Intersections of star-shaped sets

Theorem 6.1.1 Consider a collection B of sets in the coordinate space of dimension n and let

be a fixed integer. If every countable subfamily containing not necessarily different members of B has a star-shaped intersection whose kernel is at least k-dimensional then the intersection of all the members in B is a star-shaped set whose kernel is at least k-dimensional.

The proof is actually an induction on the dimension of the embedding space. In case of the coordinate line of dimension n=1 any star-shaped set isconvex and, by Klee's theorem 4.1.6, the intersection of all the members in B is non-empty and convex (especially star-shaped). If the intersection contains at least two different points then it is of dimension 1 and the proof is finished independently of the values k=0 or 1. Suppose now that the intersection is a singleton:

(6.1)

(for the sake of simplicity countable subfamilies will be labelled by natural numbers as usual to avoid double superscripts). We are going to prove that there exists a sequence of the members in B whose intersection reduces to a single point too. According to 6.1 for any natural number m there exists a set B(m) in B such that

In a similar way let B(- m) be a set in B such that

By our assumption the intersection

(6.2)

is star-shaped (especially convex) which means that it must be reduced to a singleton. Otherwise we have a segment in 6.2 containing x together with points having arbitrarily small rational distance 1/m from x which is a contradiction. Suppose that the statement is true for the coordinate space of dimension at most n - 1. By the help of the inductive hypothesis one can prove the following lemma which is the key step in the proof of theorem 1.1.

Lemma 6.1.2 Under conditions of theorem 6.1.1 the intersection of all the members in B is non-empty and it contains a k-dimensional convex subset.

Using 6.1.2 the proof of theorem 6.1.1 can be finished as follows. Let

be the intersection of all the members in B. We should check that V is star-shaped and its kernel is at least k-dimensional. Consider a new collection

(6.3)

M(γ) contains the points of B(γ) from which any point in V can be visible. Consider a countable subfamily M(1), ..., M(m), ... together with the associated sets B(1), ..., B(m), ... and let

be the intersections of the corresponding countable family of sets. Choose a point p in Ker K. Since V is a subset in K

for any element v in V and i=1, 2, ... Therefore p is in M. Especially M is a subset in K. This means that any element of M is visible from p, i.e.

(6.4)

Relation 6.4 says that we can apply lemma 6.1.2 to the collection 6.3:

and the intersection contains an at least k-dimensional convex subset. To finish the proof observe that

(6.5)

because the left hand side contains just the points of V from which any point in V can be visible, cf. 6.3. Therefore V is a star-shaped set and Ker V contains an at least k-dimensional convex subset. The proof of the key lemma 6.1.2 is based on the inductive hypothesis. Two different cases should be considered.

I. First case. Suppose that for some countable subfamily B(1), ..., B(m), ... the intersection K of the sets is at most of dimension n - 1. Then the maximal dimension of a convex subset M in K is also less than the dimension of the embedding space. Let B(1), ..., B(m), ... be chosen in such a way thatthe following minimax condition is satisfied: the maximum of the dimension of convex subsets in the intersection is as small as possible. This means that if we can inscribe a τ-dimensional convex subset into K as that of maximal dimension, then the intersection of any countable subfamily contains an at least τ-dimensional convex subset.

Lemma 6.1.3 If the family

satisfies the minimax condition then

where M is a convex subset of maximal dimension in K.

Proof Suppose, in contrary, that we have a point p in Ker K which is not in the affine hull of M. Then the convex hull of the union of M and p would be a greater dimensional convex subset in K than M.

Figure 36: A convex subset of maximal dimension in K.

Conditions for M are

(M1) M is convex,

(M2) M is a subset in K,

(M3) M is of dimension τ.

Consider the intersection of the affine hulls of M as it runs through the subsets satisfying M1, M2 and M3. We have by lemma 6.1.3 that

where H is an affine subspace of dimension at most τ. Suppose that the dimension of the affine subspace H associated with the countable family B(1), ..., B(m), ... satisfying the minimax condition is as great as possible. Choose an arbitrary countable subfamily B*(1), ..., B*(m), ... with intersection K* and let

(6.6)

be the union of the subfamilies with intersection

Recall that T contains a convex subset of dimension at least τ but T is a subset in K. Therefore 6.6 also satisfies the minimax condition. Thus

for the dimension of the associated affine subspace

where M' is a τ-dimensional convex subset in T. Especially, M' is a subset in K. Therefore

showing that H=L, i.e. the associated affine subspaces coincide because of the maximality condition for the dimension of H. On the other hand lemma 1.3 implies again that Ker T is a subset in L and, consequently,

Finally we apply the inductive hypothesis to the family of sets

(6.7)

in the coordinate space of dimension at most τ. The intersection of sets in 6.7 is contained in the intersection of all the members in B together with its k-dimensional kernel which is a convex set.

II. Second case. Suppose that for every countable subfamily has an n-dimensional intersection and let

be the collection of intersections of countable subfamilies. It can be easily seen that

(6.8)

and for any countable subfamily

(6.9)

we have a corresponding countable subfamily

(6.10)

where

for any index j. The intersection of 6.9 is just that of 6.10. Therefore the intersection of 6.9 has a non-empty interior and the same is true for the intersection of the closures of sets in 6.9. Let T be the intersection of the closures of sets in P (cf. theorem 4.1.5). Since the complement of T is expressed as the union of open subsets we can choose, by Lindelöf's theorem, a countable subcover. Taking the complement again T can be expressed as the intersection of a countable subfamily (say 6.9) of the closures:

Since the interior of T is non-empty it contains an open ball D in its interior. If D is a subset of the intersection of sets without closure operator the proof is finished. Otherwise suppose that p is a point in D such that p is not in G(1) (but p is in the closure of G(1)). Since G(1) is represented as a countable intersection of sets from B we can suppose thatp is not in B(1) for some set in B. Consider a countable subfamily B(1), ..., B(m), ... of subsets in B. The intersection

(6.11)

is a star-shaped set. Let z(1) be a point of Ker K. Since p is not in B(1) we have that p is not in K and the ray emanating from p into the opposite direction relative to z(1) does not contain points from K because they would be visible from z(1) together with p.

Figure 37: A segment.

Recall that p is an interior point of the intersection of the closures of sets in P and thus it is an interior point of the closure of K (belonging to P). So we have a segment S(1) on the line of p and z(1) such that it has no common points with K but it is in the interior of the closure of K. If the kernel of K is a subset of aff S(1) we are ready. Otherwise we can construct a two-dimensional triangle S(2) such that it is in the interior of the closure of K but there are no common points with K.

Figure 38: A triangle.

If the kernel of K is a subset of aff S(2) we are ready. Otherwise repeat the process to construct a tetrahedron S(3) such that it has no common points with K but it is in the interior of the closure of K.

Figure 39: A tetrahedron.

Repeat the algorithm as far as possible we can construct a j-dimensional simplex S(j) such that it has no common points with K but it is in the interior of the closure of K. By the constructing process,

Let τ be the number of the maximal dimension of sets in D which are disjoint from K. Then τ is greater than or equal to k but it must be less than n. It is clear because in case of τ=n there would be an n-dimensional simplex S which is disjoint from K (i.e. the interior points of S could not be limits of sequences in K) but S is a subset ofthe closure of K. Therefore

Suppose that the collection B(1), ..., B(m), ... has the greatest possible value of τ and consider the family of sets

(6.12)

where H is the affine hull of S(τ). Using the inductive hypothesis, the intersection

is a star-shaped set with kernel of dimension at least k and the proof is finished.

6.2 Excercises

Excercise 6.2.1 Prove that the star-shaped and convex sets of the coordinate line of dimension 1 coincide.

Excercise 6.2.2 Prove the one-dimensional version of Klee's theorem 4.1.6.

Excercise 6.2.3 Prove that we can apply the inductive hypothesis to the family 6.7.

Hint. Taking a countable subfamily

(6.13)

we have that the intersection of the members in 6.13 is

where T is the intersection of the countable family

Because of our assumptions T is a star-shaped set and, by the second step, its kernel is contained in H. This means that the intersection of T and H is also a star-shaped set and

Therefore

and we can use the inductive hypothesis as mentioned above.

Excercise 6.2.4 Prove that we can apply the inductive hypothesis to the family 6.12.

Let k be an arbitrary natural number and

(6.14)

Figure 40: Excercise 6.2.5.

Figure 41: Excercise 6.2.5.

Figure 42: The intersection of T(1) and T(2) (left). The kernel (right).

Figure 43: Excercise 6.2.6.

Excercise 6.2.5 Prove that every finite subfamily of 6.14 has a star-shaped intersection whose kernel is of dimension two but the intersection of all thethe sets is not star-shaped.

Let k be an arbitrary natural number and

(6.15)

where

Excercise 6.2.6 Prove that every finite subfamily of 6.15 has a star-shaped intersection whose kernel is of dimension two but the intersection of all the sets is not star-shaped.

Hint. Especially

Remark The excercise illustrates that the condition for the countable subfamilies in theorem 1.1 could not be weakened to a finite version.

7. fejezet - Separating and supporting hyperplanes

The result on the existence of separating hyperplane between two compact sets can be considered as a geometric version of Hahn-Banach's theorem on linear functionals. Its first form is an extension theorem since the property required of the functional is that it extends a given functional (defined on a subspace) without increasing the norm. The second form is a separation theorem because the property required of the hyperplane is that it separates two given convex sets. The connection, of course, is that a (closed) hyperplane is a translate of the kernel of a continuous linear functional. In finite dimensional spaces one can follow a simplified "more linear and less topological" way to develop the theory [55]. Using the classical setting of the coordinate spaces the most adequate approach is to rely not only on the basic topology and the linear structure of the space but also on the Euclidean geometry via orthogonal complements and nearest-point-type argumentations as follows.

7.1 Separating and supporting hyperplanes

In the sense of the structure theorem 1.3.8 each non-empty affine set A can be written into the formp+L, where p is an arbitrary element in A and L is a uniquely determined linear subspace.

Definition Affine sets of dimension n - 1 in the n-dimensional coordinate space are called hyperplanes.

Since the co-dimension of the associated linear subspace of a hyperplane is just one its orthogonal complement can be generated by a non-zero vector n which is unique up to a non-zero scalar multiplier. It is clear that the point q is in the hyperplane if and only if the position vector q - p (with respect to p) is orthogonal to n, i.e.

(7.1)

We have two further possible cases corresponding to the inequalities

(7.2)

The points of the space which are not in the hyperplane 7.1 are in exactly one of the so-called (open) half-spaces determined by the relations 7.2. It can be easily seen that they are non-empty disjoint convex subsets in the coordinate space. Their closures (the open half-spaces together with the hyperplane) are called closed half-spaces. If we substitute n with its additive inverse then the relations characterizing the half- spaces come into each other but they do not change as pointsets. The sides of a hyperplane mean the half-spaces determined by the hyperplane.

Definition The subsets D and E in the coordinate space of dimension n are called separated by the hyperplane L if they are in different sides of L. Strictly separation means that the subsets are in different open sides of the hyperplane.

Figure 44: The nearest-point-type argumentation.

The nearest-point-type argumentation. Let p be a point in the coordinate space of dimension n and consider a compact convex set K in the space such that p is not in K. By a standard compactness argumentation it follows that there exists a point q in K where the distance

is attained at. Consider now the vector n:=p - q. If L is the orthogonal complement to n then the standard conclusion is that the hyperplane q+L separates p and K. To prove this observation suppose, in contrary, that K has a point z in the open half space containing p. The segment s(z,q) is in K because of the convexity and it must intersect the interior of the Thales ball around the diameter s(p,q). Therefore we have a point in K which is closer to p than q. This is a contradiction as figure 43 shows. In what follows we shall use this kind of argumentation in more general cases by substituting p with a compact convex set.

Theorem 7.1.1 Let D and E be compact subsets in the coordinate space of dimension n. They are strictly separated if and only if their convex hulls are disjoint.

Proof If the sets are strictly separated then their convex hulls must bedisjoint because they are contained in different open half-spaces determined by the separating hyperplane. To prove the converse statement first of all recall that the convex hull of a compact set is also compact 2.2.2. Suppose that the convex hulls are disjoint and consider the distance

between them. By a standard compactness argument it follows that there are points p in conv D and q in conv E such that

Let n be the difference vector of the points where the minimal distance is attained at and consider the linear subspace L which is orthogonal to n. Using a standard nearest-point-type argumentation it can be easily seen that the open band determined by the hyperplanes p+L and q+L is disjoint from both conv D and conv E. Therefore the hyperplane bisecting the band strictly separates the sets conv D and conv E together with D and E, respectively. ▮

Definition We say that a hyperplane bounds a set D if D is contained in one of the half spaces. If the hyperplane H bounding D has a common point p with the set D then H is said to support D at the point p.

Theorem 7.1.2 (The existence theorem of supporting hyperplanes) Let K be a closed convex subset in the coordinate space ofdimension n. Then for any boundary point p in K there exists a hyperplane supporting K at p.

Proof If dim K < n then any hyperplane containing K is a supporting hyperplane at each point of K. In what follows we are going to construct supporting hyperplanes passing through the boundary points of K. The proof is actually an inductive process on the dimension of the embedding space. The case of the coordinate plane. Let K be a closed convex subset of dimension 2 in the coordinate plane and suppose that the origin is one of the boundary points by translating K if necessary. Consider the central projection of K through the origin to the unit circle. The image of K is a connected arc belonging to a central angle with measure at most π because of the convexity of K.

Figure 45: The case of the coordinate plane.

Therefore there exists a diagonal of the circle which bounds this arc together with the set K. The case of higher dimensional coordinate spaces.

Figure 46: The orthogonal projection.

Let p be an arbitrary boundary point and consider a hyperplane H of dimension n - 1 passing through p in the coordinate space of dimension n. If H supports K then there is nothing to prove. Otherwise let K' be the intersection of H and K. It is a closed convex subset of maximal dimension[7] in H as the coordinate space of dimension n - 1. Taking the supporting hyperplane at p in H to the intersection K' we have a hyperplane H' of dimension n - 2. Let P' be the orthogonal complement to H'. Then P' is of dimension two. Consider the orthogonal projection π(K) in P'. Since H' is a supporting hyperplane to K' in H the point π(p) supports π(K') in the common line l of H and P'.Therefore π(p) is on the boundary of the projected set π(K) as well and we can consider the supporting line l' in P' to the set π(K) at π(p).

Figure 47: The supporting hyperplane.

The corresponding supporting hyperplane to K at p is just the affine hull of the union of H' and l'. ▮

Theorem 7.1.3 (The converse of the existence theorem.) Let K be a closed n- dimensional convex set in the coordinate space of dimension n. If for any boundary point p of K there exits a supporting hyperplane passing through p then K is convex.

Proof If K is just the coordinate space of dimension n then we have nothing to prove. Therefore we can suppose that there exists an element v which is not in K. Let w be in the interior of K and suppose that p is its boundary point on the segment s(v,w). Since w is contained in K together with an open neighbourhood we have that the supporting hyperplane at p does not contain w and, consequently, the hyperplane strictly separates the endpoints v and w. At the same time v and the set K are separated. We have just proved that if v is not in K then there exists a supporting hyperplane of K such that v and K are separated. In fact the opposite half space to that containing K contains v in its interior. Let Ω be the intersection of closed half spaces containing K. It is clear that K is a subset of Ω and the equality of K and Ω follows from the fact that each point v in the complement of K is in the complement of Ω. Therefore Ω is a subsetof K. But the intersection of closed half spaces is convex. So is K as was to be proved. ▮

Remark The theorem can be considered as an external characterization of convexity of sets. Another possibility of such a characterization is to prove that if a closed subset satisfies the nearest-point property then it is convex, see also excercise 7.4.2.

Corollary 7.1.4 Let K be a closed n-dimensional convex set in the coordinate space of dimension n. K is convex if and only if for any boundary point p of K there exits a supporting hyperplane passing through p.

7.2 Krein-Milman's theorem

The theorem belongs to the basis of the theory of convex sets. The presented version for convex sets in the finite dimensional coordinate space was proved by H. Minkowski. The generalization of this result to infinite dimensional topological vector spaces involves an additional closure operator too. It is due to Krein and Milman (1940).

Figure 48: Hermann Minkowski, 1864-1909.

Definition Let K be a convex subset in the space. The point p in K is called an extreme point if the punctured set K - {p} is also convex. Ext K denotes the set of the extreme points or, in an equivalent terminology, the profile of K.

Remark We have some simple examples for extreme points like the endpoints of segments. Another type of examples are related to convex closed domains in the plane bounded by smooth curves with curvature having no zeros. In this case all of the boundary points are extreme points.

Theorem 7.2.1 (Krein-Milman) If K is a non-empty compact convex set then it is the convex hull of its extreme points,i.e.

Proof Let K be a non-empty compact convex set in the coordinate space of dimension n. The inclusion

is trivial and, consequently, it is enough to prove that each element q in K can be expressed as a convex combination of extreme points of K. We use an induction on the dimension of the space. If n=1 then K is a closed bounded interval with the endpoints as extreme points. Therefore q can be obviously expressed as a convex combination of them. Suppose that the statement is true for thecoordinate spaces of dimension at most n - 1. If q is an extreme point then the proof is finished. Otherwise K can not be punctured at q without loosing the convexity. Therefore there exists a segment

such that

Using that K is compact we can suppose that both endpoints of this segment are on the boundary of K. Consider the supporting hyperplanes

Then

(7.3)

are convex compact sets of dimension

By the inductive hypothesis each endpoint of the segment can be expressed as a convex combination of the extreme points of 7.3. To finish the proof we are going to prove that the extreme points of the intersections 7.3 are extreme points of the set K as well. If (for example) i=1 and z is an extreme point of the set

(7.4)

then segments containing z in their relative interiors could not run in the hyperplane because z is an extreme point of 7.4. But they could not intersect the hyperplane because it is a supporting hyperplane for K. Therefore we have no such a segment and z is an extreme point of K as was to be proved. ▮

Corollary 7.2.2 The set of extreme points of a compact convex set is non-empty.

Remark An alternative argumentation: let K be a compact convex set and consider the point where the norm function attains its maximum at (the furthest point of K from the origin). We can easily prove that it must be an extreme point of K, see also excercise 7.4.7.

7.3 Support functions and Minkowski functionals

In this section we consider two convex functions which are closely related to the geometry of convex sets. Because their applications are limited in this material most of the basic properties will be left as an excercise.

7.3.1 Minkowski functionals

Definition A compact set in the coordinate space of dimension n is called a body if it is the closure of its interior.

Definition Let K be a convex body containing the origin in its interior. The Minkowski functional induced by Kis defined as

(7.5)

where t > 0. Minkowski spaces are finite dimensional real vector spaces equipped with a Minkowski functional.

It can be easily seen that the Minkowski functional is positively 1-homogeneous and subadditive: for any positive real number t

Subadditivity together with positively homogenity imply convexity as well. The symmetry of K with respect to the origin is equivalent to the absolute homogenity (or reversibility)

(7.6)

(cf. properties of a norm in the space). In the preamble to his fourth problem presented at the International Mathematical Congress in Paris (1900) Hilbert suggested the examination of geometries standing next to Euclidean one in the sense that they satisfy much of Euclidean's axioms except some (tipically one) of them. In the classical non-Euclidean geometry the axiom taking to fail is the famous parallel postulate. Another type of geometry standing next to Euclidean one is the geometry of normed spaces (Minkowski spaces). The crucial test is not the parallelism but the congruence via the group of linear isometries. In his pioneering work on the geometry of numbers Minkowski realized that the best way for the investigation of normed spaces (Minkowski spaces) is to consider the unit sphere or the unit ball. Conversely, if we have a compact convex subset K containing the origin in its interior then the functional 7.5 measures the length of vectors in an adequate way. Moreover the distance function d with respect to l can be also introduced in the usual way as lengths of difference vectors. Geometrically the length is a simple ratio in the sense that

where l* is an arbitrary function (norm) measuring the lenght of vectors and v* is the boundary point of K corresponding to the ray from the origin into the given direction v. The functional l was first defined by H. Minkowski to provide a method of obtaining a norm together with a topology in very general linear spaces.

Definition By a linear isometry with respect to the Minkowski functional l we mean a linear transformation (invertible linear map) preserving the Minkowskian lenght of vectors.

The study of isometries or distance-preserving mappings of a Minkowski space is greatly simplified by a celebrated theorem due to Mazur and Ulam [53] for normed spaces or Minkowski spaces with reversible Minkowski functionals. The theorem states that any surjective isometry can be written as the composition of an invertible linear map and a translation. The linear part is, of course, automatically a linear isometry of the space. Therefore a general Minkowski space does not admit isometries of many types onto itself. In general translations, the identity map and the central symmetry with respect to the origin are the only examples.

Remark The converse of the problem of isometries seems to be also important: how to find an invariant convex body under a given subgroup of invertible linear transformations? The problem will be discussed in chapter 10.

7.3.2 Support functions

Definition Let S be a non-empty convex set. The support function of S is an extended real-valued function defined as

(7.7)

The domain of an extended real-valued function is the set of points where the function has finite values at.

Extended real valued functions admit the positive or negative infinity as values. The set of extended real numbers has an ordering extending the natural ordering on the set of reals. Therefore the sup-operator can not cause any confusion in the definition of the support function. To clarify the geometric meaning of the support functions associated with convex sets we need the notion of polar sets.

Definition Let L be a non-empty subset in the coordinate space of dimension n. The polar set L* is defined as

Remark In case of a singleton the polar set is just the space itself if the origin is the only element of L. Otherwise if p is the only element in L but different from the origin then the characteristic property of the elements in L* is equivalent to the inequality

which gives a closed half-space. It can be easily seen that the bounding hyperplane is orthogonal to p.

In the sense of Riesz representation theorem each linear functional in the dual space can be expressed as

where n is a uniquely determined vector belongig to f. Conversely the right hand side of the formula defines a linear functional. Using the identification between f and n the polar set L* can be identified with the set of all linear functionals having supremum at most one on L.

Theorem 7.3.1 Let K be a compact convex body containing the origin in its interior. The support function of K is equal to the Minkowski functional of the polar set K*.

Proof Since K is compact the domain of the support function is the coordinate space of dimension n. On the other hand the origin in the interior of K implies that the support function is a positive definite (positively 1-homogeneous and convex) function. The equivalence

is also obvious. Therefore the unit ball with respect to the support function is just the polar set of K. ▮

To justify the name "support" we present the following theorem.

Theorem 7.3.2 Let K be a compact convex set and consider a non-zero element v in the coordinate space of dimension n. The hyperplane H

supports K at the point where the supremum 7.7 is attained at.

Proof The hyperplane H bounds K because for any element p in K

On the other hand the point where the supremum 7.7 is attained at is a common point of H and K. ▮

Remark The distance of H from the origin is just

(7.8)

7.3.3 Radon planes

Keeping in mind Hilbert's motivations why to investigate the geometry of normed spaces (Minkowski spaces) we illustrate one more problem which is closely related to the basic notions of Euclidean geometry: orthogonality/normality [45], see also [53]. It is very important to see that the way of measuring angles between vectors in a Minkowski space is a non-trivial problem. In what follows wesketch a way to introduce the notion of orthogonal vectors. Sometimes they are called normal to each other provided that the role of the vectors is symmetric.

Definition Taking two unit vectors v and w in a Minkowski plane we say that v is normal to w if the line passing through v into the direction w supports the unit disk at v.

Definition The Radon plane is such a Minkowski plane for which normality is symmetric. The unit circles of Radon planes are called Radon curves.

For the characterization of Radon curves and examples see the corresponding list of excercises.

7.4 Excercises

Excercise 7.4.1 Generalize the nearest-point-type argumentation by substituting p with a closed convex subset in the coordinate space of dimension n.

Excercise 7.4.2 Prove that if K is a closed convex set then for any point q in the space there exists a uniquely determined point in K which is the nearest point of K to q. In other words closed convex sets satisfy the nearest-point property with respect to the Euclidean distance.

Excercise 7.4.3 Find a convex set such that it does not satisfy the nearest-point property with respect to the taxicab norm.

Excercise 7.4.4 Find the extreme points of the convex hull of the points

in the coordinate plane.

Excercise 7.4.5 Prove that for any compact convex set in the coordinate plane the profile is a closed set.

Excercise 7.4.6 Find an example for a compact convex set in the coordinate space of dimension three such that the profile is not closed.

Hint. Divide a cylinder into two parts by a plane containing the axis.

Excercise 7.4.7 Prove that the maximum of a continuous convex function on a compact convex set is attained at one of its extreme points.

Hint. Suppose, in contrary, that the statement is false and represent the elements as convex combinations of some extreme points. The convexity of the function gives an upper bound for the values of the function in terms of the values at the extreme points.

Excercise 7.4.8 Find the set of extreme points of a closed half-space.

Excercise 7.4.9 Let K be a closed convex subset in the coordinate space of dimension n and suppose that the hyperplane H supports K at the point p. Prove that p is an extreme point of the intersection of K and H if and only if it is an extreme point of K.

Excercise 7.4.10 Prove that the Minkowski functional is positively 1-homogeneous and subadditive: for any positive real number t

Excercise 7.4.11 Prove that each norm is just the Minkowski functional induced by the unit ball.

Excercise 7.4.12 Find the Minkowski functional l induced by the convex hull of the points

see the taxicab norm 1.48.

Excercise 7.4.13 Find the Minkowski functional l induced by the convex hull of the points

see the maximum norm.

Excercise 7.4.14 Find the Minkowski functional induced by an ellipse centered at the origin. How to deduce l as a norm coming from an inner product?

Excercise 7.4.15 Find a symmetric convex body K such that the induced Minkowski space has the minimal set of isometries.

Excercise 7.4.16 Find the Minkowski functional associated to the closed disk

and prove that the reflection about the line joining the origin and the center of the disk is a linear isometry of the Minkowski space.

Excercise 7.4.17 Prove that the domain of the support function is convex.

Excercise 7.4.18 Prove that the support function is a positively 1-homogeneous convex function on its domain.

Excercise 7.4.19 Find the polar set of the convex hull of the points

in the coordinate plane.

Excercise 7.4.20 Find the polar set of the convex hull of the points

in the coordinate plane.

Excercise 7.4.21 Find the polar sets of disks and ellipses centered at the origin in the coordinate plane.

Excercise 7.4.22 Find the polar set of a tetrahedron in the coordinate space of dimension three.

Excercise 7.4.23 Find the polar set of the cube with vertices

in the coordinate space of dimension three.

Excercise 7.4.24 Find the polar set of the octahedron with vertices

in the coordinate space of dimension three.

Excercise 7.4.25 Prove that the polar set is a closed convex set containing the origin.

Hint. For the basic properties of polar sets see chapter 9.

Excercise 7.4.26 Find the support function of the convex hull of the points

in the coordinate plane.

Excercise 7.4.27 Find the support function of the convex hull of the points

in the coordinate plane.

Excercise 7.4.28 Find the support functions of disks and ellipses centered at the origin in the coordinate plane.

Excercise 7.4.29 Find an example to illustrate that the normality in Minkowski planes is not a symmetric relation in general.

Hint. Consider squares (see the taxicab norm or the maximum norm) or regular octagons in the plane.

Excercise 7.4.30 Prove that ellipses and regular hexagons areRadon curves.

Excercise 7.4.31 Prove that the polar of a Radon curve is also a Radon curve.

A differentiable curve

is parameterized by Minkowskian arclength if its derivatives have unit length with respect to the Minkowski functional at each parameter s, i.e. l(c'(s))=1. Let c be a twice-differentiable parametrization of the unit circle of a Minkowski plane by Minkowski arclength.

Excercise 7.4.32 Prove that c is a Radon curve if and only if the Wronskian

is constant.

Hint. Using the Minkowskian arclenght parametrization c'(s)=c(t(s)). The Radon curve property requires that c'(t(s)) is parallel to c(s). By differentiation we have that c''(s) is parallel to c(s) which is equivalent to the vanishing of the derivative of the Wronskian determinant.

Excercise 7.4.33 Prove that for any Radon-curve c the line joining the origin and c(s) sweeps out equal areas during equal intervals of time.

Hint. Use that

gives the area swept out from a to t; see Kepler's second law of planetary motions.

8. fejezet - Kirchberger's separation theorem

Kirchberger's theorem (1902) gives a combinatorial criteria for the existence of a separating hyperplane between compact sets in the space. To prove the theorem we need the notion of extreme points of a convex set and Krein-Milman's theorem related to the convex hull of the extreme points.

8.1 Kirchberger's separation theorem

Let K be a convex subset in the space. Recall that the point p in K is called an extreme point if the punctured set K - {p} is also convex. Krein-Milman's theorem 7.2.1 states that each compact convex set K is the convex hull of its extreme points.

Definition Let D be a subset of the coordinate space of dimension n. The point q has the k-point simplicial property[8] with respect to D if there exists a simplex spanned by the elements p(1), ..., p(r) such that r is at most k and q is in the convex hull of p(1), ..., p(r).

Remark In what follows D(k) denotes the elements of the convex hull having the k-point simplicial property with respect to D.

Lemma 8.1.1 Let D and E be compact subsets in the coordinate space of dimensionn such that

If v is an extreme point of the intersection of the convex hulls, i and j are the smallest integers such that

then i+j is at most n+2.

Proof According to Carathéodory's theorem 2.2.1 we have that

Therefore

(8.1)

If (for example) i=1 then inequalities 8.1 say that

and the situation is similar in case of j=1. In what follows suppose that both i and j have values at least 2. Since v is in D(i) we have a simplex spanned by some elements p(1), ..., p(i) such that v is in their convex hull. Using that i cannot be reduced we have that there are no vanishing coefficients in the convex combination presenting v.

Figure 49: The proof of Lemma 8.1.1.

Therefore v can be included in a ball Γ(D) of dimension i - 1 in conv D; especially the inclusion is in the affine hull of p(1), ..., p(i). Similarly, there exists a ball Γ(E) of dimension j - 1 in conv E such that Γ(E) contains v. But v is an extremal point of the intersection of the convex hulls.

Figure 50: A contradiction.

Figure 51: Possible intersections.

This means that the intersection of the balls must be a singleton containing only v and, consequently,

showing that

as was to be proved. ▮

Theorem 8.1.2 (Kirchberger, Paul). Let D and E be compact sets in the coordinate space of dimension n. They can be strictly separated by a hyperplane if and only if for each subset T of at most n+2 elements in D U E the sets

can be strictly separated by a hyperplane.

Proof If D and E can be strictly separated by a hyperplane then of course their subsets can be strictly separated. Suppose that D and E can not be strictly separated and, consequently, their convex hulls have a non-empty intersection. If v is an extreme point of the intersection of the convex hulls then, by the previous lemma,

where i+j is at most n+2. For the sake of definiteness suppose that

for some elements p(1), ..., p(i) in D and q(1), ..., q(j) in E. Taking the set

the intersections

can not be strictly separated. By contraposition it follows that if for each subset T of at most n+2 elements in D U E the sets

can be strictly separated by a hyperplane then D and E can be strictly separated.

Kirchberger's theorem has a great significance in the solution of the problem how to decide the separability of finite point-sets. If we want to investigate directly the intersection of the convex hulls whether they are disjoint or not we should solve the equation

under the additional conditions

Therefore we have m+k unknown parameters in a system of linear equations containing n+2 members, where m and k are the numbers of elements of the sets D and E, n is the dimension of the space (the number of coordinates). In case of m+k >> n+2 it seems to be very hard to solve because of the enormous amount of free parameters. Kirchberger's theorem provides a method to divide the solutionof the problem into several but elementary parts: after choosing elements v(1), ..., v(m') in D and w(1), ..., w(k') in E, respectively, the problem is reduced to the solution of the system

Here m'+k' is at most n+2 (the number of equations).

8.2 Separation by spherical surfaces

In what follows we reformulate Kirchberger's theorem for spherical separation by the help of the stereographic projection.

Definition The sets D and E in the coordinate space of dimension n is strictly separated by a sphere G if one of the following statements holds:

- all the points of A are inside and all thepoints of B are outside of G,

- all the points of B are inside and all the points of A are outside of G.

Figure 52: The stereographic projection (the first version).

The method to transfer the separation by hyperplanes into a spherical separation is based on the stereographic projection. It is a widely used process in cartography as a way to make a flat map of the earth. Because the earth is spherical, any map must distort shapes or sizes to some degree. The rule for stereographic projection has a nice geometric description. Think of the earth as a sphere sitting on the plane of the paper. (The south pole touches the paper.) Now imagine a light bulb at the north pole p which shines through the sphere. Each point on the sphere has a "shadow" to determine itsown place on the map. The south pole works as the center point of the map. Latitudes appear as circles around the center (longitudes appear as lines passing through the center of the map). Objects near the south pole are not stretched very much but the equator is twice as big on the map as on the sphere. The north pole gets sent off to infinity. Because the sphere and the plane appearin many areas of mathematics and its applications, so does the stereographic projection. It plays an important role in diverse fields including complex analysis, cartography, geology, and photography. In some applications (see complex analysis) the image of the north pole is taken at the infinity. In terms of a pure topological language the sphere is homeomorphic to the one point compactification of the plane. The stereographic projection has the followingimportant properties:

(i) it is conformal (it preserves the angle at which curves cross each other)

(ii) it is a circle preserving map (lines in the plane are considered circles with infinite radius).

Circles on a sphere come from intersections with (hyper)planes. If the plane contains the pole p of the projection then the image of the circle will be a line which can be also considered as a circle with infinite radius. It is typical in the applications. Sometimes the projection is taken with respect tothe plane H passing through the equator of the sphere. Since the projections on different (but parallel) planes can be transfer into each other by a central similarity through the point p they share the properties (i) and (ii). In what follows we use the projection onto the plane of the equator together with an analytical description to enjoy all the advantages of a dimension-free approach.

Figure 53: The stereographic projection (the second version).

Analytic description. Let S be the unit sphere centered at the origin in the coordinate space of dimension n+1. The points on S will be denoted by pairs of the form (v,s), where v is in the coordinate plane H spanned by the first n canonical basis vector and s is a real number between - 1 and 1. Let p=( 0,1) be the point of the projection ("north pole"). The condition for the intersection of the line passing through (v,s) and p with H is the vanishing of the last coordinate of a point on the parametric line

as t runs through the real numbers. Therefore

and, consequently,

Its inverse works formally as

where s can be expressed by taking the norm of the vectors v and v':

because the element (v, s) has unit length. Therefore

and, consequently, the inverse transformation can be given as

Especially,

Excercise 8.2.1 Prove that

Hint. Recall that

The result says that the stereographic projection is actually the restriction of an inversion with center p. Therefore the properties (i) and (ii) of the stereographic projection can be concluded from the corresponding properties of the inversion. The advantage of proving the properties for inversions is that we can use the standard calculus and linear algebra without adaptation to (hyper)surfaces.

Excercise 8.2.2 Prove that the Jacobian matrix of the inversion is proportional of the unit matrix at each point of the space except the center.

Remark In the sense of the previous excercise the inversion is conformal because the angles are defined in terms of tangent objects. In order to see the conformal property of the stereographic projection in the classical case we can use the following more elementary argumentation: consider the tangent (hyper)plane H' to the sphere atp. H' is parallel to the (hyper)plane H of the equator and, consequently, for any line l in H we have a parallel line l' in H' by intersecting H' with the plane P spanned by l and the pole p of the projection. The common part of P and S is a circle C'. It is clear that l' is tangential to C' and, consequently, the angle between two (intersecting )lines in the plane H is the same as the angle between their inverse circles (which is just the angle between their tangent lines passing through the common point p).

Excercise 8.2.3 Prove that the stereographic projection is a circle/sphere preserving map.

Hint. Taking the difference of the canonical equations it can be easily seen that the intersection of two spheres is also a sphere although the dimension decreases in general. Therefore itis enough to prove that the inversions are sphere preserving maps.

Theorem 8.2.4 Let D and E be compact sets in the coordinate space of dimension n. They can be strictly separated by a sphere if and only if for each subset T of at most n+3 elements in D U E the sets

can be strictly separated by a sphere.

Proof Consider the coordinate space of dimension n as a hyperplane

in the space of dimension n+1 and let D' and E' be the inverse images of the given sets under the stereographic projection of the unit sphere in the embedding space. The original version of Kirchberger's theorem 8.1.2 says that D' and E' can be strictly separated by a hyperplane L (of dimension n) in the embedding space. Since it is a strict separation we can suppose, without loss of the generality, that the separating hyperplane does not contain the pole of the projection. Therefore the image of the intersection of L and S under the projection is a (non-degenerate) sphere G in the coordinate hyperplane of dimension n. G separates D and E as was to be proved. ▮

Figure 54: A counterexample.

The figure shows that the number n+3 can not be reduced. Although we have five circles to separate the points belonging to different letters in all the quadruples

the sets D={p(1), p(2), p(3)} and E={q(1), q(2)} can not be separated by circles.

8.3 The best affine approximation

Another application of Kirchberger's original theorem is the solution of the problem how to find the best affine approximation for a finite collection F of given points. Geometrically we want to find a hyperplane as "close" to F as possible. Functions with one variables. Let r > 2 different points be given inthe coordinate plane:

(8.2)

The problem is to find an affine function f(x)=ax+b for which the largest error

(8.3)

is as small as possible. The figure illustrates two approximations of 8.2 with r=5. The negative slope gives a better approximation with respect to 8.3.

Figure 55: The best affine approximation.

The solution of the problem. Let f be a given affine function and consider the sets

If

then A and B can be strictly separated by a zero-dimensional hyperplane, i.e. a point x(0) in the coordinate axis[9]. If we rotate the graph of the function around the point (x(0), f(x(0)) with a sufficiently small angle we have a better approximation as the figure shows: for the function f (having a positive slope)

and, consequently,

The rotation of the graph around the point (x(0), f(x(0))) with a sufficiently small angle into the clockwise direction reduces the absolute value of the difference at the points of both A and B. It should be sufficiently small because the rotation may in fact increase the difference (with absolute value less than δ) at other points of the domain. Therefore if f is one of the best approximations of 8.2 with respect to 8.3 then

To prove the converse statement consider a function f in such a way that the convex hulls of the sets A and B intersect each other. Suppose, in contrary, that f' is a better approximation than f. Then the graph of f' must be lower than the graph of f at each point of A. Especially the same must be true at each point of conv A. On the other hand the graph of f' must be higher than the graph of f at each point of B. Especially the same must be true at each point of conv B. This obviously gives a contradiction to the non-empty intersection of the convex hulls. We have just proved that f is the best approximation if and only if the convex hulls of the sets A and B have a non-empty intersection. Therefore A and B can not be strictly separated which is equivalent, by Kirchberger's separation theorem, to the condition that we have a subset T of A U B containing at most three points such that the sets

can not be strictly separated. In other words the solutions of the original problem involving r given points are the solutions of the reduced problems involving some three points among the given ones: choose a collection of three points containing T. For the sake of simplicity consider the triplet

(8.4)

ordered in such a way that x(1)<x(2)<x(3). Then we have the following two possibilities:

or

Therefore one of the systems of linear equations

or

depending on the ordering of the second coordinates should be solved. Geometrically we need a mid-line in the triangle formed by the points (x(i),y(i)), where i=1, 2, 3. After calculating the best approximation for each triplet we can explicitly determine the errors with respect to the full system of points 8.2 to choose the best one.

Functions with two variables. Let r > 3 different points be given in the coordinate spaceof dimension three:

(8.5)

The problem is to find an affine function

for which the largest error

(8.6)

is as small as possible. The solution of the problem. Let f be a given affine function and consider the sets:

If

then A and B can be strictly separated by a line l in the coordinate plane (x,y). It can be considered as the orthogonal projection of the line

in the space (especially in the graph of the affine function f). Rotating the graph of f around the line l' with a sufficiently small angle we can decrease the (common) error at the points of both A and B. This results in a better approximation than f in a similar way as above. Therefore if f is one of the best approximations of 8.5 with respect to 8.6 then

To prove the converse statement consider a function f in such a way that the convex hulls of the sets A and B intersect each other. Suppose, in contrary, that f' is a better approximation than f. Then the graph of f' must be lower than the graph of f at each point of A. Especially the same must be true at each point of conv A. On the other hand the graph of f' must be higher than the graph of f at each point of B. Especially the same must be true at each point of conv B. This obviously gives a contradiction to the non-empty intersection of the convex hulls. We have just proved that f is the best approximation if and only if the convex hulls of the sets A and B have a non-empty intersection. Therefore A and B can not be strictly separated which is equivalent, by Kirchberger's separation theorem, to the condition that we have a subset T of A U B containing at most four points such that the sets

can not be strictly separated. In other words the solutions of the original problem involving r given points are the solutions of the reduced problems involving some four points among the given ones: choose a collection of four points containing T.

8.4 Excercises

Excercise 8.4.1 Let D be the set of vertices of a square in the coordinate plane. Find the sets

Excercise 8.4.2 Find an example to show that the Kirchberger number n+2 can not be reduced.

Hint. The pairs of points on the same diagonals of a square can not be separated by a line but any three of them can be strictly separated.

Excercise 8.4.3 Prove or disprove that the sets

can be separated by a line in the coordinate plane. Find the equation of the separating line if exists.

Excercise 8.4.4 Prove or disprove that the sets

can be separated by a line in the coordinate plane. Find the equation of the separating line if exists.

Excercise 8.4.5 Prove or disprove that the sets

can be separated by a line in the coordinate plane. Find the equation of the separating line if exists.

Excercise 8.4.6 Prove or disprove that the sets

and

can be separated by a plane in the coordinate space of dimension three. Find the equation of the separating plane if exists.

Excercise 8.4.7 Find the error for the best affine approximation to each subset of three points in

Find the best affine approximation to all the points.

Excercise 8.4.8 Find the best affine approximation of the set of points

Excercise 8.4.9 How to generalize the best approximation problem and the solution to the coordinate space of dimension n?

9. fejezet - Convex polytopes and polyhedra

9.1 Vertices, edges, faces

Definition The convex hull of finitely many points in the space is called a convex polytope. Two-dimensional convex polytopes in the plane are convex polygons. Three-dimensional convex polytopes in the coordinate space of dimension three are convex polyhedra.

Remark Simplices (see section 23) are convex polytopes.

Proposition 9.1.1 Convex polytopes have finitely many extreme points called vertices.

Proof Let K:=conv {q(1), ..., q(m)} be a convex polytope and suppose that K has an extreme point q not among the points

(9.1)

Then each element of 9.1 belongs to the punctured set K - {q} which is convex because of our hypothesis. Therefore the smallest convex set containing the points 9.1 is K - {q} which is a contradiction. ▮

According to Krein-Milman's theorem 7.2.1 the following corollary is obvious.

Corollary 9.1.2 Each convex polytope is the convex hull of its vertices.

Theorem 9.1.3 Non-empty compact intersections of finitelymany closed half-spaces are convex polytopes.

Proof Let

(9.2)

be closed half-spaces bonded by the hyperplanes

(9.3)

respectively. We will use an induction on the dimension of the embedding coordinate space to prove that the (convex) set

has finitely many extreme points. In case of n=1 it is obvious because the convex compact sets are the closed bounded intervals which are convex polytopes. Suppose that the statement is true in the coordinate spaces of dimension at most n - 1. If

and v is an extreme point of K then v must be on the boundary of K. Otherwise we can consider an open ball around v and the convexity hurts by cancelling this point from K. Therefore v must be one of the hyperplanes 9.3 which means that

By our hypothesis sets on the right hand side contain only finitely many points. So does ext K. Using Krein-Milman's theorem 7.2.1 we have that K is a convex polytope as a convex hull of finitely many points in the space.

Let L be a non-empty subset in the coordinate space of dimension n. The polar set of L is defined as

For polar sets (excercises and comments) see also subsection 7.3.2.

Lemma 9.1.4 The polar set of a non-empty set L is a closed convex set containing the origin. Moreover

(9.4)

(9.5)

(9.6)

If K is a closed convex set containing the origin then

(9.7)

Proof The only property which does not follow directly from the definition of the polar set is 9.7. Let (for a moment) L=K* be the polar set of K. If p is in K then for all element n in L

which means, by definition, that p is in L*=(K*)* as well. Therefore K is a subset in L*. To prove the converse suppose that q is not in K and consider a hyperplane H such that q is strictly separated from K by H. The hyperplane is given by an equation of the form

(9.8)

Using the notation

for the normal vector of the hyperplane we can write equation 9.8 in a more compact form of the Hesse equation

(9.9)

Since the origin is in K the inequality

(9.10)

determines the half-space containing K. Therefore each element p in K satisfies inequality 9.10. This means that n is in L. At the same time we have that the inner product of n and q must be greater than 1 because the hyperplane 9.9 strictly separates q and K. So we have that q is not in L*=(K*)*. The argumentation shows that the complement of K is a subset of thecomplement of L* and, consequently, L* is a subset of K. Therefore L*=K as was to be proved.

Theorem 9.1.5 Each n-dimensional convex polytope in the coordinate space of dimension n is the intersection of finitely many closed half-spaces.

Proof Let K:=conv {q(1), ..., q(m)} be a convex polytope of dimension n. Taking a translate of K if necessary we can suppose that the origin is in the interior of K without loss of generality. Consider the polar set L=K*. In the first step we are going to show that L is the intersection of the closed half-spaces

i=1, ..., m. From the definition of the polar set the inclusion

is obvious. On the other hand for any convex combination

relations

imply that

proving the converse of the inclusion. The polar set has just been presented as the intersection of finitely many closed half spaces. In the second step we are going to prove that the polar set is compact. According to the previous lemma it is enough to prove the boundedness. By our assumption the origin is in the interior of K together with an open ball B centered at 0 with a sufficiently small radius r. Then, by 9.5, L is a subset in B* which means that L is bounded. Therefore it is a non-empty (the origin always belongs to the polar set) compact intersection of finitely many closed half-spaces which implies, by theorem 9.1.3, that it is a convex polytope: L=conv {q*(1), ..., q*(m*)}. Repeating the argumentation in the first step with L instead of K we have that L* is the intersection of the half-spaces

where i=1, ..., m*. Finally L*=(K*)*=K according to the duality property 9.7. ▮

Theorem 9.1.6 (The structure theorem of convex polytopes) Let P be an n-dimensional convex polytope in the coordinate space of dimension n and consider a minimal representation of P as the intersection of finitely many closed half-spaces, i.e. suppose that none of them can be cancelled among the half-spaces. Such a minimal representation is unique up to the order of the half-spaces and the intersections of the bounding hyperplanes with P are convex polytopes of dimension n - 1.

Definition The intersections of the n-dimensional convex polytope P with the bounding hyperplanes in the minimal representation are called (n - 1) - dimensional faces or facets of the polytope. We can introduce inductively the notion of k - dimensional faces. Especially the one-dimensional faces are called edges and the 0 - dimensional faces are referred as vertices of the polytope.

9.2 Euler's and Descartes theorem

Euler's theorem can be considered as the first obstruction of building convex polyhedra. It contains a famous relationship among the numbers of vertices, edges and facets.

Figure 56: Leonard Euler, 1707-1783.

Theorem 9.2.1 (Euler, Leonard) The numbers v, e and f of vertices, edges and facets of a convex polyhedron are related by Euler's formula

(9.11)

Proof The affine hull (plane) of any facet divides the space into two half-spaces such that the polyhedron is entirely contained in exactly one of them. This half-space will be called positive. After choosing a facet F consider a point c in the negative half-space with respect to F in such a way that c is contained in the positive half-spaces with respect to the facets except the distinguished one. Use a central projection through c to present a connected finite graph in the plane of F by the projections of the vertices and edges of the polyhedron. This graph has v vertices, e edges and the projections of the facets except the distinguished one appear as convex polygons without common interior points. The number of these convex polygons is just f - 1. Consider the complement of F in the plane instead of the missing facet. Thus we have a partition of the plane of F into f domains without common interior points. Take the next steps. Steps of first type. If we have a circle in the graph delete one of its edges. The output is a connected graph (the missing edge is avoidable along the complement "arc" of the circle) with the same number of vertices. The number of domains in the partition decreases together with the number of edges. Therefore their difference and, consequently, the Euler characteristic 9.11 remains invariant. Repeat steps of first type as far as possible. Steps of second type. If we have no circles in the graph then there must be vertices of degree 1 (such a vertex can be found as the starting or the endpoint of the longest walk in the graph). Delete a vertex of degree 1 together with the corresponding edge. The output is a connected graph because the connectedness does not reflect to vertices with only one way to reach. The numbers of vertices andedges are reduced in this way but their difference and, consequently, the Euler characteristic 9.11 remains invariant. Repeat steps of second type as far as possible. The end of the algorithm is a graph containing only one vertex without edges and we have only one domain in the partition of the plane of F. Therefore v - e+f=1 - 0+1=2 as was to be stated.

Remark The higher dimensional Euler-formula is

(9.12)

where n is the dimension of the space and f(k) denotes the number of k-dimensional facets (k=0, ..., n - 1).

Excercise 9.2.2 Find all convex polyhedra with f=5.

Hint. Since the total sum of the facets is five we have only p triangular and q rectangular facets, where p+q=5. We have that

and the possible values are p=2 and q=3 (a triangular based prism) or p=4 and q=1 (a rectangular based pyramid).

Excercise 9.2.3 Find all convex polyhedra with f=6.

Definition The defect of a vertex V of a convex polyhedron is 2π minus the sum of the angles at the corners of the facets at V.

The second obstruction of building convex polyhedra is that each defect must be positive. Another result related to the defects of a convex polyhedra is Descartes's theorem. It will be applied to the characterization of regular polyhedra.

Figure 57: René Descartes, 1596-1650.

Theorem 9.2.4 (Descartes, René) The sum of the defects of vertices of a convex polyhedra is just 4π.

Proof Let f(m) be the number of convex m - gons among the facets of the polyhedra. Since the sum of the measures of the internal angles is (m - 2)π we have that the sum of the defects is

where

and

because each edge belongs to exactly two facets. Using Euler's theorem we have that the sum of the defects

as was to be stated. ▮

Excercise 9.2.5 Find all convex polyhedra with regular triangles as facets.

Hint. For the so-called Deltahedron's problem see [6] and [32] Theorem 45.6.

Theorem 9.2.6 (Cauchy's rigidity theorem, 1813) If there exists an edge- and facet- preserving correspondence between the vertices of two convex polyhedra such that the corresponding facets are congruent then they are congruent.

Proof The rigorous proof of the theorem involves some tools of combinatorics and (colored) graph theory [1], see also [21] and [39]. An elementary proof can be found in [32]. We summarize its basic steps. Let P(1) and P(2) be two convex polyhedra satisfying the conditions in the rigidity theorem. Cauchy's original idea is to study how the dihedral angles compare along corresponding edges. If all the dihedral angles are the same then we can build P(1)and P(2) step by step into congruent figures. Let each edge of P(1) be labelled by +, - or no mark according as its dihedral angle is less than, greater than or equal to the corresponding dihedral angle in P(2). At each vertex we intersect the polyhedra with sufficiently small spheres. This produces spherical polygons called vertex figure whose interior angles are just the dihedral angles. Therefore its vertices inherit markings+ or - from the edges. By our conditions the corresponding spherical polygons have equal sides. The basic question is that what about the interior angles. Using Steinitz's comparison lemma [32] (lemma 45.3) one can prove that either all corresponding angles are equal or, as we make a circuit of the polygon ignoring unmarked vertices, the sign must change at least four times[10]. To finish the proof we count the total number of changes of sign in two different ways. For the sake of simplicity suppose that all edges are marked + or - and let N be the sum over all the vertices of the number of changes of sign of edges around that vertex. It follows that N is at least 4v, where v is the number of vertices. On the other hand let us count by facets. On a triangular face two adjacent edges must have the same sign. Therefore such a face can contribute at most two changes of sign to its three vertices. Facets of n sides can contribute at most n changes of sign if n is even or n - 1 if n is odd. Especially

Euler's theorem says that

i.e.

and, consequently,

which is a contradiction. Therefore we have no any change of sign and all corresponding dihedral angles are equal. ▮

Remark If there are some marked and some unmarked edges we can imitate the previous proof using only those vertices and edges that are labelled. Such a configuration is called a net. A net-face is formed by any maximal union of facets of the polyhedron which are not separated by edges of the net. The Euler's formula for nets is

and the argument of the proof still works.

Excercise 9.2.7 Find an authentic proof of the rigidity theorem for tetrahedra.

Hint. Let

be two tetrahedra. By our assumption the correspondence

(9.13)

of the vertices gives facets with congruent edges. Since 9.13 can be uniquely extended to an affine transformation

and the translation part is obviously an isometry we have that the linear part is also an isometry. Therefore T(2) is the image of T(1) under an isometry. In other words they are congruent.

Excercise 9.2.8 How to generalize the argumentation of the proof of Cauchy's rigidity theorem to more general polyhedra?

Hint. Construct a class of convex polyhedra admitting a kind of inductive proof starting from tetrahedrons.

9.3 Regular polyhedra

The Platonic solids (regular convex polyhedra) have been known since antiquity. The ancient Greeks studied them extensively. Some sources (such as Proclus) credit Pythagoras with their discovery. Other evidence suggests he may have only been familiar with the tetrahedron, cube and dodecahedron and the discovery of the octahedron and icosahedron belong to Theaetetus, a contemporary of Plato. Theaetetus gave a mathematical description of all five Platonic solids. He may have been responsible for the first known proof that there are no other convex regular polyhedra. Euclid also gave a complete mathematical description of the Platonic solids in the Elements. Propositions 13 - 17 in Book XIII describe the construction of the tetrahedron, octahedron, cube, icosahedron and dodecahedron. For each solid Euclid found the ratio of the diameter of the circumscribed sphere to the edge length. InProposition 18 he argues that there are no further convex regular polyhedra.

Figure 58: The tetrahedron.

Definition A convex polygon in the plane is called regular if it is equiangular and equilateral, i.e. all internal angles are equal in measure and all sides have the same length. The facets of a regular polyhedron are congruent regular polygons with the same dihedral angle along each edge and the same number of edges concur at each vertex: the pair (m,n) is the symbol of the regular polyhedra if the facets are regular m-gons and n is the common number of edges meeting at each vertex).

Figure 59: The cube.

Theorem 9.3.1 The possible symbols of a regular convex polyhedron are

Proof Since each vertex has the same defect and their sum is 4π (Descartes' theorem) we have that each vertex has the same positive defect:

(9.14)

where

is the common measure of the internal angles in a regular m-gon. From here

because the value of m is at least three. It follows that n is less than six and, consequently, its possible values are 3, 4 or 5. If n=3 then 9.14 says that m < 6 and, consequently, its possible values are 3, 4 or 5. In case of n=4 we have by 9.14 that the only possible value of m is 3. Finally, if we substitute n=5 into equation 9.14 we have that m=3 (because it must be less than 10/3) ▮

Figure 60: The octahedron.

Remark The regular tetrahedron is of type (3,3). The cube is of type (4,3). The convex hull of the centers of the facets of a cube is the so-called octahedron of type (3,4). The cube and the octahedron are "dual" (see also polar sets in subsection 7.3.2. The edges of a regular octahedron can be subdivided in the golden ratio so that the resulting vertices define a regular icosahedron of type (3,5). It can be done by first placing vectors along the octahedron's edges such that each facet is bounded by a circle, then similarly subdividing each edge into the golden mean along the direction of its vector. The convex hull of the centers of the facets of an icosahedron is a dodecahedron of type (5,3). They are also "dual". The convex hull of the centers of the facets of a tetrahedron is a tetrahedron. It is "self-dual" (see also polar sets in subsection 7.3.2).

Figure 61: The icosahedron.

Figure 62: The dodecahedron.

In what follows we summarize the basic data of regular polyhedra.

10. fejezet - Generalized conics

The idea of generalization of classical conics is a periodic phenomenon in the history of mathematics. There are lots of points of view of investigations. Generalized conics (especially polyellipses as the additive versions of lemniscates) were investigated from the viewpoint of approximation theory [24], see also [23]. On the other hand these geometric objects appear in optimization problems in a natural way [30], see also [41] and [31]. Another point of view in the literature [47] is the theory of equidistant sets: the United Nations Convention on the Law of the Sea (Article 15) establishes that, in absence of any previous agreement, the delimitation of the territorial sea between countries occurs exactly on the median line every point of which is equidistant of the nearest points to each country. The classical conics can be always realized as sets of equidistant points from two given subsets (circles) in the plane. Here we have another type of generalization together with applications in Minkowski geometry and geometric tomography.

Instead of finite sums integration of the Euclidean distance over the set of foci (curves, surfaces, integration domains) will be used to generalize the classical conics. According to the philosophy of integration (partitions, integral sums) conics defined by this way are just limits of conics in the discrete sense. Therefore it is a purely topological way of the generalization (cf. Weiszfeld's problem and Erdős-Vincze's theorem). There are general difficulties in explicite computations and adaptation to the standard tools in differential geometry such as parametrization and curvature; see e.g. elliptic integrals in case of circular conics in the space. To develop a kind of theory of circular (generalized) conics [56], see also [57], we need subtle estimations [2] and [49] for ellipticintegrals and the Gaussian hypergeometric function. As a similar trend computer simulations, algorithms and estimations can be used instead of the classical tools.

10.1 A panoramic view

Let G be a subset of the Euclidean coordinate space. A generalized conic is a set of points with the same average distance from the points in G. First of all we consider some examples how to calculate such an average distance of a single point from a point-set. The method can be realized in several ways from classical (discrete) means to integration over the set of foci. In most of important cases the common feature of functions measuring the average distance is the convexity. They also satisfy a kind of growth condition. Therefore the level sets are compact convex subsets in the space bounded by compact convex hypersurfaces. They are called generalized conics.In what follows we present some examples and basic facts of the theory of generalized conics.

Example If G is a finite set of points in the space then the average distance can be calculated as the arithmetic mean

(10.1)

of distances from the points p(1), ..., p(m) of G. Hypersurfaces of the form F(p)=const. are called polyellipses or polyellipsoids depending on the dimension of the embedding coordinate space. The points p(1), ..., p(m) are called focuses. We have the usual notion of ellipses in case of two different focuses in the coordinate plane.

It is natural to take any other types of mean or their weighted versionsinstead of the standard arithmetic one in formula 10.1. The most important discrete cases are polyellipses with the classical arithmetic mean to calculate the average Euclidean distance from the elements of a finite point-set and lemniscates (with the classical geometric mean to calculate the average Euclidean distance from the elements of a finite point-set). Lemniscates in the plane play a central role in the theory of approximation in the sense that polynomial approximations of holomorphic functions can be interpreted as approximations of curves with lemniscates. In terms of algebra we speak about the roots of polynomials (in terms of geometry we speak about their foci). Endre Vázsonyi posed the problem whether the polyellipses (as the additive versions of lemniscates) have the same approximating property by increasing of the number of the foci or not. The answer is negative (see Erdős-Vincze's theorem [24], see also [60] and chapter 11). To include hyperbolas as a special case of generalized conics we can admit a simple weighted sum of distances instead of means. Parabolas can be given as a special case if not only single points but hyperplanes are also admitted as the element of the set of foci. The pure case of such a construction is presented in the following example.

Example If G isa finite set

(10.2)

of hyperplanes in the coordinate space of dimension n then the average distance can be calculated as the arithmetic mean

(10.3)

of distances from the hyperplanes 10.2. Especially let

be the canonical basis and consider the hyperplanes

In terms of the coordinates of p we have

and hypersurfaces of the form F(p)=const. are just spheres with respect to the 1-norm. They can be also considered as a generalization of conics.

It is a natural question whether how we can calculate the average distance of a single point of the space from a set consisting of infinitely many points. Consider first of all a curve Γ in the space. In order to calculate the average distance of thepoint p from Γ divide the curve into m parts with the same arc-length. After choosing a point from each part let us define the function

(10.4)

where s(1)= ... =s(m) is the common arc-length of the pieces and γ(1), ..., γ(m) are points on the curve from the corresponding pieces of the partition. Under reasonable conditions

In view of this argumentation we can formulate the following definition.

Definition Let Γ be a bounded orientable submanifold[11] in the coordinate space of dimension n with finite positive measure (arc-length, area or volume). The average distance is measured as the integral

(10.5)

Hypersurfaces of the form F(p)=const. are called generalized conics with Γ as the set of focuses.

In this sense generalized conics are "limits" of sequences of polyellipses or polyellipsoids 10.1; cf. Weissfeld's problem of the topological closure of the set of polyellipses in the plane. To generalize the pure case of hyperplanes 10.3 in a similar way we can use the submanifolds of Grassmannians. By taking submanifolds of the product of the coordinate space with Grassmannians or flag manifolds [38] mixed cases can be also presented. Let Γ be a subset of dimension n. The integral

is just the volume of the body C(p) bounded by Γ in the horizontal hyperplane of dimension n and the upper half of the right circular cone with opening angle π/2. It has a vertical axis to the horizontal hyperplane at the vertex p.

Figure 63: The body C(p).

Theorem 10.1.1 The function F is convex satisfying the growth condition

(10.6)

Proof Convexity is clear because the integrand is a convex function of the variable p for any fixed element γ in Γ. Since Γ is bounded it is contained in a ball around the origin with a finite radius K. Then

implies the inequality

Integrating both side over Γ

as was to be stated.

Excercise 10.1.2 Prove that the levels of the function F are bounded.

Hint. Suppose, in contrary, that the level set

contains a sequence of points p(1), ..., p(m), ... such that the norms of the elements p(i)'s tend to the infinity. Then

which contradicts to the growth condition 10.6.

Corollary 10.1.3 F has a global minimizer.

Proof The statement follows from the Weierstrass's theorem [13] : if all the level sets of a continuous function defined on a non-empty closed set in the coordinate space of dimension n are bounded then the function has a global minimizer.

Excercise 10.1.4 Prove Weierstrass's theorem: if all the level sets of a continuous functiondefined on a non-empty closed set in the coordinate space of dimension n are bounded then the function has a global minimizer.

Excercise 10.1.5 Under what conditions can we provide the unicity of the minimizer?

Hint. Find a condition for the function F to be strictly convex.

10.2 Special types of generalized conics

In this section we are going to present more explicit examples of circular conics (conics with acircle as the set of foci) in the coordinate space of dimension three. Conics in the coordinate plane with squares as the set of focuses will be also considered. In both cases we use integration to compute the average distance. Integration of the Euclidean distance over subsets in the space is crucial for finding alternatives of Euclidean geometry. Let O(n) be the group of linear isometries in the Euclidean space and consider a subgroup H in the orthogonal group together with a compact convex subset K containing the origin in its interior such that

(i) it is not an ellipsoid (ellipsoid problem),

(ii) it is invariant under the elements of H and

(iii) its boundary is a smooth hypersurface (regularity condition).

By the second condition H is a subgroup of the linear isometry group O'(n) of the Minkowski space induced bythe Minkowski functional of K. The first condition shows that O'(n) is a real subgroup in the orthogonal group. In other words the Minkowski geometry based on the functional associated to K is an alternative of the Euclidean geometry[12] for the subgroup H. One of the main applications of the generalized conics' theory is to present convex bodies satisfying conditions (i) - (iii).

Definition The subgroup H is called transitive on the Euclidean unit sphere if any two elements of the unit sphere can be transported into each other by a transformation from H.

If the subgroup H is transitive on the Euclidean unit sphere then the Euclidean geometry is the only possible one for H. The list of transitive subgroups in O(n) are

and

For the classification see [11], [12] and [29]. In what follows we present alternatives of the Euclidean geometry for non-transitive subgroups of the orthogonal group [57]. Theoretically we have two different cases: reducible and irreducible subgroups.

10.2.1 The case of reducible subgroups

If the group is reducible then there exists a non-trivial invariant linear subspace of dimension 0 < k < n in the coordinate space under the elements of the subgroup. This subspace cuts a (k - 1)- dimensional sphere S from the unit sphere in the embedding space. In this case S plays the role of the set of foci. To avoid the theoretical and technical difficulties of higher dimensional coordinate spaces we restrict ourselves to the space of dimension three (circular conics) [56]. Let

(10.7)

be the unit circle in the (x, y)-coordinate plane and

The surface of the form

(10.8)

is a generalized conic with foci S(1) in the Euclidean space. According to the invariance of the set of foci under the rotation around the z-axis 10.8 is a revolution surface with generatrix

(10.9)

in the (y, z)-coordinate plane.

Figure 64: The generalized conic 10.8.

Lemma 10.2.1 The generalized conic 10.8 is not an ellipsoid.

Proof It is enough to prove that the generatrix

is not an ellipse in the (y, z)-coordinate plane. If y=0 then we have that

On the other hand, if z=0 then the solutions of the equation

are just y=+1 or - 1. Therefore the only possible ellipse has the parametric form

(10.10)

Figure 65: The generatrix and its approximating ellipse.

The figure shows the generatrix (pointstyle) and its approximating ellipse. Consider the auxiliary function

Then v(0)=v(π/2)=8 but

where

is the standard elliptic integral. Using that

(10.11)

(Vuorinen's conjecture, for the proof see [2]) the inequality

(10.12)

shows that v(s) is not a constant function. ▮

Corollary 10.2.2 The generalized conic 10.8 induces a non-Euclidean Minkowski functional l such that the Euclidean isometries leaving the set of foci 10.7 invariant form a subgroup of the linear isometries with respect to l.

Proof It is clear that generalized conics together with the induced Minkowski functionals heritage all symmetry properties of the set of foci. Onthe other hand the previous lemma shows that L can not be arised from an inner product.

In general the group of linear isometries of a non-Euclidean Minkowski space is trivial. Results like 10.2.2 give examples on geometric spaces having more and more rich linear isometry group up to the Euclidean geometry.

10.2.2 The case of irreducible subgroups

Definition A transformation group H is closed if for any point p theorbit

is a closed subset.

Example The group of rotations in the plane around the origin with rational magnitudes is not a closed subgroup.

Excercise 10.2.3 Prove that each non-transitive closed subgroup in the orthogonal group of the Euclidean plane is finite.

Hint. The proof is a kind of nearest-point-type argumentation. Take a point u on the unit circle and consider its orbit P(u) under H. Since H is not transitive there exists a point u' on the unit circle which is not in P(u). By the closedness we can consider the closest points of P(u) to u' into the two possible directions. They form a circular arc C' of positive length such that its (relative) interior is disjoint from P(u). The nearest-point property implies that the relative interiors of the circular arcs P(C') must be pairwise disjoint. Then H must be finite because the sum of the lengths is obviously bounded.

Remark The result says that the alternative geometries of dimension two for non-transitive closed subgroups in O(2) always can be realized by Minkowski functionals induced by polyellipses in the plane. A similar theorem can be formulated in case of the coordinate space of dimension three because of Wang's theorem [62] stating that the dimension of a non-transitive closed subgroup inO(3) is just 0 or 1. In case of a one-dimensional subgroup the unit component is actually a one-parameter family of rotations around a line. Choose a finite "unit component" - invariant system of points on this line we can consider the image of the system under mappings from different connected components (it is enough to choose only one mapping from each component). Since the number of the components is finite we have a finite collection of points which is invariant under the whole group.

In case of higher dimensional spaces the convex hull of non-trivial orbits[13] will play the role of the set of foci.

Lemma 10.2.4 Let H be a closed subgroup in the orthogonal group. It is irreducible if and only if the origin is the interior point of the convex hull of any non-trivial orbit under H.

Proof First of all note that the convex hulls of the orbits are obviously invariant under H. If H is irreducible and the origin is not a point of the convex hull of a non-trivial orbit then we can use a simple nearest-point-type argumentation to present a contradiction as follows: taking the uniquely determined nearest point of the convex hull to the origin it can be easily seen that it must be a fixed point of any element of H. This contradicts to the irreducibility. If the origin is not in the interior of the convex hull of a non-trivial orbit P(u) we can consider the common part T of supporting hyperplanes at the origin. Since 0 is not in P(u) it can not be an extreme point of the convex hull which means that T is at least a one-dimensional linear subspace. On the other hand it is invariant under H which is a contradiction. Therefore the origin must be in the interior of the convex hull of any non-trivial orbit. The converse of the statement is trivial.

Excercise 10.2.5 Prove that invariant ellipsoids must be Euclidean balls in case of any irreducible subgroup of the orthogonal group.

Hint. Suppose that H contains orthogonal transformations with respect to different inner products. For the sake of simplicity let one of them be the canonical inner product and consider another one given by a symmetric matrix M. If Mv=λv for some nonzero vector v then for any transformation h in H we have

because both h and its inverse are orthogonal transformations with respect to both M and the canonical inner product. Therefore eigenvectors with eigenvalue λ form an invariant linear subspace of H which must be the whole space according to the irreducibility. Thus Mv=λv for all vectors and the balls with respect to these inner products coincide.

Example Consider the group of symmetries of the square

(10.13)

centered at the origin in the Euclidean plane. The convex hull of any non-trivial orbit is a convex polygon having singularities at the vertices. For example the orbit

induces the supremum norm

To avoid the singularities at the vertices consider the function

Curves of the form F(x,y)=const. are just generalized conics with the square 10.13 as the set of foci. In what follows we investigate the level curve C passing through the point (2,1).

Excercise 10.2.6 Prove that C is not a circle: recall that invariant ellipses under the symmetry group of the square must be circles.

Hint. According to the symmetric role of the variables x, t and y, s we cancalculate the coordinate functions

of the gradient vector field:

Using these formulas consider the auxiliary function

to measure the difference between the gradient vectors of the family of generalized conics and circles. We have

which is obviously different from zero.

The general case is discussed via the following theorem of the alternatives.

Definition Let z be a fixed element of the unit sphere S in the coordinate space of dimension n and consider its orbit under H. The minimax point of the orbit is such a point z* on the sphere where the minimum

is attained at.

Consider the function

By the help of the standard calculus [38] it can be seen that it is a smooth convex function on the real line. Define

and take the functions

and

It is clear that

On the other hand one of the hypersurfaces F(p)=c and F*(p)=c must be different from the sphere unless the mapping

is constant. It is impossible because H is not transitive.

Excercise 10.2.7 Prove that if the mapping

is constant then

and H is transitive on the Euclidean unit sphere.

Hint. Taking any element in P(z) its antipole shows that the constant is just the diameter of the sphere. Finally we have the following theorem of the alternatives.

Theorem 10.2.8 (Theorem of the alternatives) If H is non-transitive on the unit sphere, closed and irreducible, z in S and c is the common value of the functions F and F* at the minimax point z* then at least one of the hypersurfaces

induces a non-Euclidean Minkowski functional l such that H is the subgroup of the linear isometries with respect to l.

Finally we slightly modify the rate of the level in such a way that c* > c. A continuity-type argumentation shows that the generalized conic belonging to the level c* induces a non-Euclidean regular Minkowski functional for the subgroup H. Regularity follows easily because the set of foci is containedin the interior of these convex hypersurfaces. The theorem of the alternatives motivates the following definition.

Definition Let Γ be a bounded orientable submanifold in the coordinate space of dimension n with finite positive measure. If g is a strictly monotone increasing convex function on the non-negative real numbers with initial value g(0)=0 and

(10.14)

then hypersurfaces of the form F(g)(p)=const. are called generalized conics with distorsion g.

Excercise 10.2.9 Prove that 10.14 is a convex function satisfying the growth condition 10.6

Hint. Use that

Theorem 10.2.10 If H is a non-transitive closed subgroup of the orthogonal group then the alternative geometry for H always can be realized by Minkowski functionals associated to generalized conics in the space.

10.3 Applications in Geometric Tomography

If the Euclidean distance is substituted by the distance function arising from the 1-norm then we have another notion of generalized conics with applications in geometric tomography [58]. Geometrictomography focuses on problems of reconstructing homogeneous ( often convex) objects from tomographic data (X-rays, projections, sections etc.). A key theorem in this area states that any convex planar body can be determined by parallel X-rays in a set of four directions whose slopes have a transcendental cross-ratio [26].

Let K be a compact body (a compact set is called a body if it is the closure of its interior) in the coordinate plane,

(10.15)

where

A(K) is the area of K and

is the distance function induced by the taxicab norm (1-norm)

Excercise 10.3.1 Using the notatios

prove that

Hint. For the proof see [57].

Corollary 10.3.2 The global minimizer of the generalized conic function associated to K bisects the area in the sense that the vertical and horizontal lines through this point cut the body K into two parts with equal area.

Using these formulas the partial derivatives can be expressed by the Cavalieri's principle as follows:

where the functions X and Y give the one-dimensional measure of sections with the coordinate lines, respectively. These are called X-ray functions into the coordinate directions. Lebesgue's differentiation theorem shows that

holds almost everywhere. Therefore the function 10.15 measuring the average "taxicab" distance can be considered as an accumulation of coordinate X-rays' information. The following figures show different polygons with the same coordinate X-rays to illustrate the difficulties of the reconstruction.

Figure 66: A convex polygon with coordinate X-rays I.

Figure 67: A convex polygon with coordinate X-rays II.

As we can see the inner singularities (together with the endpoints of the support intervals) of the coordinate X-ray functions determine a grid having the possible vertices. This means (among others) that we have only finitely many different polygons with the same coordinate X-rays. Another important consequence is that any convex polygon can be successively determined[14] by three X-rays because we can choose the third direction in such a way that it is not parallel to any line joining the points of the grid.

Excercise 10.3.3 Prove that the singularities of the coordinate X-rays correspond to the vertices of the convex polygon in the plane.

Hint. Any convex polygon P in the plane can be written into the form

where f is a convex, g is a concave function of the variable. Therefore the vertical X-ray function has the simple form Y(x)=g(x) - f(x). On the other hand the support of Y is an interval [a,b]. It can be easily seen that the difference of a concave and a convex function is concave and, consequently, the X-ray functions of convex compact planar bodies are continuous and differentiable almost anywhere. Moreover,if Y is differentiable at an inner point x then

where the signs + and - refer to the right and left hand side derivatives of the functions, respectively. Since f is convex,

and, consequently, for a concave function,

which means that

i.e. Y is differentiable at x if and only if P has no vertex along the vertical line at x.

Definition The box of a compact convex planar body means the circumscribed rectangle with parallel sides to the coordinate directions.

Excercise 10.3.4 Prove that the set of compact convex planar bodies having the same box is convex in the sense that if K and L have a common box then it isa box for any convex combination

too. Conclude that

(10.16)

(10.17)

Express the coordinate X-rays of M in terms of the coordinate X-rays of K and L.

Hint. Use the infimal convolution of functions.

Inequalities 10.16 and 10.17 imply, by the Cavalieri's principle, that the volume is a concave function on the set of compact convex planar bodies having a common box; in general see the Brunn-Minkowski inequality in subsection 4.2.1. As another consequence we have

For generalizations and applications see [59]. The goal of this section is to present a positive reconstructing result for the class of generalized 1-conics

The proof will be presented in a more general situation. Let K be a compact body and consider the distance function

induced by the p-norm, where p is greater or equal than one. Define the class of generalized p-conics as the boundary of the level sets

(10.18)

of generalized p-conic functions

Theorem 10.3.5 Let C be a solid generalized p-conic and suppose that C* is a compact body with the same area as C. If the generalized p-conic functions associated to C and C* coincide then C is equal to C* except on a set of measure zero.

Proof Let C be the level set 10.18 of the generalized p-conic function associated with K and suppose that C* is a compact body with the same area as C such that the generalized p-conic functions associated with C and C* coincide. By the Fubini theorem

(10.19)

and thus

(10.20)

Since

(10.21)

and

(10.22)

we have that

(10.23)

But C and C* have the same area and, consequently, equality holds in formula 10.23. Therefore equalities hold in both 10.21 and 10.22. This means that C does not contain any subset of positive measure which is disjoint from C* and vice versa:

(10.24)

showing that C is equal to C* except on a set of measure zero. ▮

Corollary 10.3.6 Let C and C* be generalized p-conics. If the generalized p-conic functions associated to C and C* coincide then C=C*.

Proof Since both of the sets C and C* are generalized p-conics they have a symmetric role in 10.23 showing that they have the same area. To finish the proof we use the previous theorem for the compact convex sets C and C*.

Corollary 10.3.7 Generalized 1-conics are determined by their X-rays in the coordinate directions among compact bodies.

Proof In case of p=1 the condition for the generalized conic functions implies automatically that C and C* have the same area. To finish the proof we use the previous theorem for the sets C and C*.

Remark The problem of determination of convex bodies by a finite set of X-rays was posed by P. C. Hammer at the A.M.S. Symposium on Convexity in 1961. X-rays can be considered as original but special examples for tomographic quantities. Another question is how to recognize a convex planar body from its angle function. The notion was introduced by J. Kincses [34]. Conditions for distinguishability are formulated in terms of the tangent homomorphism using thetheory of dynamical systems [33]. Like the coordinate X-ray pictures the author prove that distinguishability is typical in the sense of Baire category: a set is of first category if it is the countable union of nowhere dense sets (not typical cases) and of second category otherwise (typical cases).

Example Consider the square

for any point (x,y) in N

and circles can be interpreted as generalized 1-conics with N as the set foci. Therefore they are determined by their X-rays into the coordinate directions among compact bodies.

Excercise 10.3.8 Prove that for any point in N

Excercise 10.3.9 Consider the triangle

Prove that for any point in the box of T

Excercise 10.3.10 Let P be a convex polygon in the plane. Prove that generalized conics with P as the set of foci are the union of adjacent algebraic curves of degree at most three.

Hint. For the partition of the level curves use the grid of the polygon determined by the vertices.

Excercise 10.3.11 Consider the unit disk

Prove that for any point in the box of D

11. fejezet - Erdős-Vincze's theorem

Let a set of points in the Euclidean plane be given. We are going to investigate the levels of the function measuring the sum of distances from the elements of the point-set which are called focuses. Levels with only one focus are circles. In case of two different points as focuses they are ellipses in the usual sense. If the set of focuses consists of more than two points then we have the so-called polyellipses. In what follows we investigate them from the viewpoint of differential geometry. Lower and upper bounds for the curvature involving explicit constants will be given. They depend on the number of the focuses, the rate of the level and the global minimum of the function measuring the sum of the distances. The minimizer is characterized by E. Vázsonyi (Weiszfeld) [63]. We also present the solution of Weissfeld's problem: any convex closed curve in the plane can be approximated by polyellipses with a sufficiently large number of focuses? The answer is negative as a theorem due to P. Erdős and I. Vincze states. Especially the Hausdorff distances of circumscribed polyellipses from a regular triangle have a positive lower bound. In other words a regular triangle is not an accumulation point of the set of circumscribed polyellipses with respect to the Hausdorff metric.

Figure 68: Weiszfeld Endre, 1916-2003.

Figure 69: Erdős Pál, 1913-1996.

11.1 Polyellipses in the plane

Definition Let p(1), ..., p(n) be not necessarily different points in the coordinate plane and consider the function F defined by the formula

(11.1)

The levels of the form F(p)=c are called polyellipses with the points p(1), ..., p(n) as focuses. The multiplicity of the focuses means that how many times they appear in the sum 11.1.

Excercise 11.1.1 Prove that the function measuring the sum of distances is convex.

Hint. Use the triangle-inequality to prove the convexity of the function F. The argumentation shows that if the focuses are not collinear then it is a strictly convex function which means that equality

occurs if and only if the convex combination is trivial. Differentiability is also clear everywhere except the focuses. By the help of the more subtle calculus in section 1.6 we can determine the one-sided directional derivatives at everywhere into any direction: consider the function

then the limit

is just the one-sided directional derivative at the the critical point into the direction v. If the point q with coordinates x and y is not critical then the partial derivatives are given by the formulas

Therefore

and, consequently,

In general

(11.2)

In what follows we characterize the minimizer of the function F by Weiszfeld's theorems (see as geometric median problem). Finding such a point where the global minimum is attained at is crucial in the optimization problems. It is often referred as Fermat-problem according to the original version: how can we find a point in the plane of a triangle for which the sum of distances from the vertices is minimal? The solution of the original problem was given by Evangelista Torricelli. The problem has several types of solutions based on Viviani's theorem, Ptolemy's inequality or mechanical ideas, see e.g. [31] and [54]. For any triangle all of whose angles have less than 120 degree in measure the so-called Fermat-point or isogonic center is the point from which all the sides are seen at the angle having 120 degree in measure. Otherwise the Fermat-point is just the vertex where the critical angle is attained at or, it is exceeded.

Excercise 11.1.2 Using a standard nearest point type argumentation prove the firs obstruction: the minimizer must be in the convex hull of the focal points.

Since the convex hull of finitely many points is obviously compact the first obstruction implies the existence of the global minimizer.

Lemma 11.1.3 If the focal points are not collinear then the minimizer is uniquely determined.

Proof The condition implies that F is a strictly convex function having at most one minimizer. ▮

Excercise 11.1.4 Let four different collinear focal points be given in the plane; prove that any point of the internal segment is a minimizer of thefunction F.

Proposition 11.1.5 (Weiszfeld, Endre) The i-th focal point is a minimizer of the function F if and only if the length of the sum of the normalized position vectors of the rest of focal points with respect to this one is less than or equal to its multiplicity:

(11.3)

Proof A necessary and sufficient condition for a point to be the minimizer of a convex function is that the zero vector belongs to the set of the subgradients. According to 11.2 and theorem 1.6.4 it is equivalent to the condition

where k(i) is just the multiplicity of the i-th focal point. Since the right hand side is constant along the rays emanating from the origin, it can be uniquely determined by the help of values along the unit circle. This means that there exists a global minimum of the expression. On the other hand the Cauchy-Schwarz-Buniakowski inequality shows that the minimum is attained if we substitute the vector

which is just the sum of the normalized position vectors of the rest of focal points with respect to p(i). After substitution we have that the length of v(i) is less or equal than the multiplicity as was to be stated.

Definition A minimizer of the function F is called regular if it doesn't belong to the set of the focal points.

Proposition 11.1.6 (Weiszfeld, Endre) A necessary and sufficientcondition for a point to be a regular minimizer of the function F is that the sum of the normalized position vectors of the focal points with respect to this point is zero.

Proof Let p be a given point in the plane which is not in the set of the focal points. To characterize the minimizer we have the inequality

for any non-zero element v. Except from the normalizing factor the right hand side is linear in the variable v which means that the inequality is satisfied for any element v if and only if

as was to be proved.

In general there is no any simple way to find the minimizer. Instead of a constructing process we can use algorithms such as the gradient descent method to approximate the global minimum of convex functions on convex domains. To avoid this way we are motivated to estimate directly the minimum value of the function without any information about the exact/approximate position of the minimizer. Letthe number of the focal points be at least two and c* is the minimum of the function F attained at the point p*. For the sake of simplicity we use the notations

for the values of F at the corresponding focal points, respectively.

Theorem 11.1.7

(11.4)

Proof The upper bound follows immediately as

because of the convexity. For the derivation of the lower bound we use the triangle inequality:

and a similar result holds for c(2), ..., c(n) too. Taking the sum of these relations we have the lower bound

as was to be proved.

Proposition 11.1.8 In case of at least two focuses equality

holds if and only if the number of different focuses is exactly two, i.e. the levels of the function F are ellipses in the usual sense.

Proof The relation

implies that in case of the equality the focuses must be collinear and all of them must be a minimizer. Suppose that we have m different focuses with multiplicities k(1), ..., k(m), respectively. Then

Since the focuses are collinear we can order them in such a way that the points labelled by the first and the last indices are the extreme points of their convex hull. Theorem 11.1.5 shows that

and, consequently,

Therefore k(2)= ... =k(m - 1)=0. Using Theorem 11.1.5 again it also follows that k(1)=k(m) and, consequently, we have exactly two different focuses with the same multiplicity. This means that the levels are ellipses in the usual sense.

Remark The figure 70 shows how the lower bound can be attained in the non-trivial case of three different collinear focuses. The focuses are

Figure 70: Ellipses with three collinear focuses in the plane.

Excercise 11.1.9 Find the minimizer of the function F measuring the sum of distances from the vertices of a convex quadrilateral. What about the case of a concave deltoid? Explain how the symmetry about a line helps us finding the minimizer.

Remark Suppose that we have at least three different points as focuses. If they form a regular n-gon then the focal points are invariant under the symmetry group leaving the vertices of the regular n-gon invariant. Since the minimizer is uniquely determined it must be fixed under the elements of the symmetry group.

In what follows we illustrate the problem of parametrization of polyellipses in the plane. Consider the levels of the function F measuring the sum of the distances from the points

It can be easily seen that the second focal point is the minimizer with minimal value 2. The figure shows the levels in case of constants 2.5, 3 and 4, respectively. Since the set of the focuses are invariant under the reflections about the coordinate axes it is enough to parameterize the part in the first quadrant of the coordinate plane. Let us introduce the abbreviations

where p is an arbitrary point except the origin. In terms of the polar angle α we have the relations

(11.5)

(11.6)

by the help of using the cosine-rule. If p is a point of the polyellipse defined by the formula

then r(1)+r(3)=c - r. According to equations 11.5 and 11.6

and, consequently,

Therefore

which implies that

After substitution into 11.6

Using the distance from the origin as the parameter, the function

(11.7)

gives the first coordinates of the points of the polyellipse. By the help of Pythagorean theorem

(11.8)

In order to provide non-negative numbers under the square roots we have to restrict the coordinate functions to the interval

Remark Note that c must be greater than the minimum value 2. In case of c=3 the curve contains the focuses p(1) and p(3) as the figure shows.

By the help of standard integral formulas such as

and

the perimeter and area of a domain bounded by a parameterized curve can be calculated. The date of the following table are computed by the computer-algebra system MAPLE.

(11.9)

11.2 On the curvature of polyellipses

In what follows we are going to investigate the polyellipses from the viewpoint of differential geometry. According to the convexity of the function F these are convex curves in the plane. Let

(11.10)

be a twice continuously differentiable parameterized curve in the plane and consider the normalized tangent vector field

Differentiating equations

and

we have that

The derivative of the angle function θ is called the (signed) curvature in case of curves with unit speed. Otherwise we divide it by the length of the velocity vector w' to provide the invariance under orientation preserving re-parametrizations. As it can be seen the derivative of the angle function is just the scalar product of T' and the unit normal vector field N if they form a positively oriented (likethe canonical) basis at each parameter t:

Since

and N is orthogonal to the tangential term we have that

(11.11)

Excercise 11.2.1 Prove that the the vanishing of the curvature characterizes the line segments in the plane. What about the curvature of circles?

Remark The curvature at the point p belonging to the parameter t(0) can be characterized in the following (geometric) way: consider the circle passing through the points w(s(1)), w(t(0)) and w(s(2)). If exists then the curvature is just the reciprocal of the radius of the limit circle as s(1) and s(2) tend to t(0). In general the linear independence of the velocity and the acceleration vector at t(0) provides the existence of such a limit circle in case of twice continuously differentiable parameterized curves.

Figure 71: The geometric description of the curvature.

In terms of the function F the gradient vector field represents the normal directions along the curve which means that

where the sign refers to the orientation. Therefore

On the other hand F is constant along w and, consequently,

(11.12)

Differentiating equation 11.12 again

In terms of the Hessian matrix formed by the second order partial derivatives

and we have that

(11.13)

Figure 72: Ludwig Otto Hesse, 1811-1874.

In case of convex functions the curvature (the absolute value of the signed curvature) is

(11.14)

because the calculus of convex functions states that if F is convex then its Hessian matrix is poisitive semidefinite. Using the Laplacian (the trace of the Hessian matrix)

11.14 can be also written into the form

(11.15)

Figure 73: Pierre-Simon Laplace, 1749-1827.

Excercise 11.2.2 Find the Hessian matrix of the second order polynomial function

Since the derivative of F does not exists at the focuses in the usual sense we shall suppose that polyellipses under consideration do not pass through any of them.

Remark In their paper [41] the authors proved that if c is large enough then the polyellipse is contained between two concentric circles whose radii differ by an arbitrarily small amount, Proposition 6, p. 247. In other words the curvature function goesto being identically zero as c tends to the infinity.

Here we are going to give not only a limit, but lower and upper bounds for the curvature involving explicit constants: the number of the focuses, the rate of the level and the global minimum of the function F. In what follows w denotes the parameterization of the polyellipse

(11.16)

with focuses p(1), ..., p(n),

and the minimum c* of the function F is attained at the point p* in the plane.

Lemma 11.2.3 For the Euclidean distance from the minimizer along the curve we have the estimations

(11.17)

which means that the polyellipse is contained in the ring centered at the minimizer with the radii

Proof Taking the sum as i runs from 1 to n the triangle inequalities

give both the upper and the lower bound. ▮

Remark As a direct consequence of the previous result it follows that the convex hull of any polyellipse is a compact set; compactness and further convexity-topological properties in terms of the general notion of the norm are investigated in [30].

Corollary 11.2.4 For the area of the domain bounded by a polyellipse we have the estimations

Lemma 11.2.5 For the length of the gradient vector along the curve we have the estimations

(11.18)

Proof From the definition of the subgradient it follows that if a convex function is differentiable at w then

In case of q=p* the relation

can be derived by using the Cauchy-Schwarz-Buniakowski inequality. By inequalities 11.17

which gives the lower bound for the norm of the gradient. On the other hand, the gradient is just the sum of the unit vectors going from w to the focal points. This means that the norm of this vector couldn't be greater than the number of the focuses as was to be stated.

Remark A straightforward calculation shows that

where the double index refers to the angle of the position vectors

Lemma 11.2.6 For the Laplacian along the curve we have the estimations

(11.19)

Proof A straightforward calculation shows that

and the similar formula

holds in case of the second order derivatives with respect to the y variable. Therefore

(11.20)

For any i=1, ...,n

Using the estimations

it follows that

On the other hand

Therefore

which implies both the lower and upper bound for the Laplacian.

Theorem 11.2.7 For the curvature along the curve we have the upper bound

(11.21)

Proof Since the function F is convex its Hessian matrix is positive semi-definite. Therefore

which gives, by the help of Lemma 11.2.5 and Lemma 11.2.6, the upper bound for the curvature function.

Excercise 11.2.8 Taking the limit as c tends to the infinity prove that the curvature function goes to being identically zero.

In order to give a lower bound for the curvature we need the determinant of the matrix formed by the second order derivatives. Since

we have that

which implies the formula

(11.22)

where μ means the area of the triangle spanned by the points in the argument. By the help of the relation between the geometric and arithmetic means we have the estimation

and, consequently,

Moreover, the square function is convex which implies that

On the other hand

where μ(p(1), ..., p(n)) is the area of the convex hull of the focuses. We have just proved the following result.

Lemma 11.2.9 For any element of the polyellipse 11.16

(11.23)

Remark As the previous result shows if the focuses are not collinear then the second order partial derivatives form the coefficients of a positive definite bilinear form (cf. the expression for the second order partial derivative with respect to the first variable).

Theorem 11.2.10 Suppose that the focuses are not collinear; the reciprocal of the curvature function can be estimated by the formula

(11.24)

Proof Let λ(1) and λ(2) be the eigenvalues of the matrix consisting of the second order partial derivatives at w and suppose that they are labelled in a non-increasing order. Since λ(1) and λ(2) are just the solutions of the characteristic equation

we have that

(11.25)

On the other hand, the first eigenvalue is just the maximum of the mapping represented by the Hessian matrix at w on the unit circle, which means that

Therefore

because the Laplacian is just the sum of the eigenvalues. We have by 11.25 that

where all the terms can be estimated by inequality 11.23, Lemma 11.2.6 and Lemma 11.2.5.

11.3 Erdős-Vincze's theorem

The problem whether all the convex plane curves can be arbitrarily approximated by polyellipses under a sufficiently large number of the focuses was posed by Endre Vázsonyi (E. Weiszfeld). In case of a circle we can choose the vertices of (inscribed or circumscribed) regular n-gons as the focuses ofa polyellipses to give an approximating process as n tends to the infinity. Let r be a positive real parameter and consider the polyellipse C(r) determined by the equation

The focuses are

and C(r) passes through the points p(1) and p(2). Taking the limit as r tends to the infinity the formula

determines a curve C containing the line segment s(p(1),p(2)).

Figure 74: The limit curve as r tends to the infinity.

Figure 75: Polyellipses with parameters r=5, 15 and 30.

The "limit curve" can be arbitrarily approximated by circumscribed polyellipses with three focuses. More precisely, the Hausdorff distance of the curves goes to being zero as r tends to the infinity. In his paper[24] the authors proved that there is no way to reach a regular triangle by the help of a similar process even if the increase of the number of focuses is allowed. In what follows we present the proof of this theorem using the tools of the differential geometry of plane curves.

Theorem 11.3.1 The approximation of a regular triangle by circumscribed polyellipses always has an absolute error which couldn't be exceededeven if the number of focuses are arbitrary large.

We need some preparation to prove the statement. Let T be a regular triangle in the plane and suppose, in contrary, that there exists a sequence

(11.26)

of circumscribed polyellipses such that

We use the symbol H for notating the subgroup of isometries which leave the triangle T invariant. H consists of the identity, the reflections about the heights and the rotations around the centre with magnitude (2kπ/3), where k=1 or - 1, respectively. The first step is a kind of symmetrization. Let E be a circumscribed polyellipse defined by the equation

and consider the polyellipse E' such that E' contains all the vertices A, B and C of the triangle and its focal set is

We are going to prove that

First of all note that the role of the vertices A, B and C are absolutely symmetric as the formulas

show. Therefore E' is defined by the equation

where (for example)

Let f be an element in H and consider the polyellipse f(E) with focuses

such that the sum of distances from the focuses is just c. Because T is a subset in E we have that T is a subset in f(E) too. Therefore

Since such a formula holds for any f in H we have that c' is less or equal than 6c. Consider now the set

(11.27)

If the point q is not in the union of the convex hulls then

for any f in H. Taking the sum as f runs through the elements of H it follows that

and, consequently, q is in the complement of conv E' too. Therefore conv E' (together with T) is a subset of the union 11.27 and E' is not farther from the triangle than the boundary of Γ. On the other hand the boundary of the union 11.27 is not farther from the triangle T than E because[15]

(recall that f is an isometry leaving T invariant). This means that E' is not farther from the triangle T than E as was to be proved. In view of the symmetrization process we can suppose that the sequence 11.26 of polyellipses consists of curves passing through all the vertices with an invariant focal set under the elements of the group H. The second step is a process to avoid singularities. Let q(n) be the common point of the perpendicular bisector of the side AB and the arc of E(n) between A and B. Because of the symmetry the line l(n) passing through q(n) into the parallel direction to the side AB supports the polyellipse at q(n). Therefore the Euclidean distance between q(n) and the midpoint M of AB is just the same as the Hausdorff distance between the sets. This means that M is the limit of q(n)'s as n tends to the infinity. From the viewpoint of differential geometry we have two different cases: the point q(n) belongs to the set of the focuses or not. If it does then we ignore this point together with the focuses of the form f(q(n)) as f runs through the elements of the isometry group H of T. In this casewe substitute the polyellipse labelled by n with E'(n) as follows:

(a) the focuses are the rest of those of E(n),

(b) the curve contains all of deleted focuses.

Figure 76: The pair of curves E(n) and E'(n).

Figure 77: Similar triangles.

In what follows we prove that all the vertices of the triangle is in the interior of the convex hull of E'(n); see figure 76 (the focuses are the vertices of a regular hexagon inscribed in the unit circle centered at the origin). Let k(n) be the multiplicity of the point q(n) as the focus of the polyellipse E(n). Then the sum of distances from the focuses of E'(n) must be

where δ(n) is the Euclidean distance between q(n) and M. The formula can be easily derived by the help of using similar triangles 77:

where m is the height of the triangle and q(n) is not a fixpoint of f. It happens four times in H. On the other hand

where ''a'' is the common length of the sides. Therefore

provided that δ(n) is small enough. This means that all the vertices of the triangle is in the interior of the convex hull of E'(n) because

The comparison of the sum of distances shows that we must have focuses more than the deleted ones provided that n is great enough. In view of the second step we can consider a sequence of polyellipses E(1), ..., E(n), ... such that the focal set is invariant under the elements of the group H and the curvature goes to being zero at the point q(n) as n tends to the infinity: the convexity implies that the curvature radius at q(n) is greater than the radius of the circle passing through the points A, B and q(n). The third step is to prove that the curvature function is uniformly bounded from below which obviously gives a contradiction. Let n be great enough for q=q(n) to be in the interior of the circumscribed circle of the triangle T and consider the function F measuring the sum of distances from the elements of the focal set

of E=E(n).

Lemma 11.3.2 If R is the radius of the circumscribed circle of the triangle then

where o is the center of the triangle, and the set of the focuses is generated from the points

by the symmetry group H.

Proof Recall that the gradient vector is just the sum of the normalized position vectors of q with respect to the focuses:

Let k(0) be the multiplicity of the center if it is one of the focuses; otherwise k(0):=0. Then

because f(o)=o for any element of the symmetry group H. Since the center is the minimizer of any function measuring the sum of distances from the elements of an invariant point-set under H

and we have that the norm of the gradient at the point q is less or equal than

The estimation

is trivial. From now on we suppose that p(i) is different from the center. In order to estimate the norm of the difference of the unit vectors

and

consider first of all the case when the i-th focus and all the elements of the form f(p(i)) are in the interior of the circumscribed circle of the triangle. Since the norm of the difference of unit vectors is less or equal than 2 it follows that

(11.28)

and, consequently,

The only task is to prove inequality

for the focuses outside of the circumscribed circle. From the triangle spanned by the vectors v(i) and w(i) with the same (unit) length we have that

because the angle α(i) of these unit vectors is obviously less than 90 degree. A simple sine-rule shows that

Therefore

and, consequently,

as was to be proved. Taking the sum as f runs through the elements of H we have the upper bound for the norm of the gradient vector immediately. ▮

Lemma 11.3.3 If v is a parallel unit vector to the side AB of the triangle then

Proof Without loss of generality we can suppose that the center of the triangle coincides with the origin and AB is parallel to the y-axis. Then v=(0,1) and the second coordinate of q is zero. Using the formulas for the second order partial derivatives we should estimate the sum of terms of type

n-times. It is obviously enough to prove that

(11.29)

for any i=1, ..., n. First of all note that the case of p(i)=o is trivial (recall that q lies in the interior of the circumscribed circle and its second coordinate is zero). Suppose that p(i) is different from the origin. By the triangle inequality,

and, consequently,

For some isometry f in H, the polar angle of f(p(i)) must be between 120 and 240 (degree). Therefore

and it happens at least two times showing that estimation 11.29 holds. ▮

Now we are in the position to finish the proof of the theorem. Using the notations in the proof of the previous lemma the curvature is just

(11.30)

which is a contradiction.

Remark Inequality 11.30 involves a global minimum for the curvature along the whole arc of the polyellipse because of the symmetry. The method presented in the proof can be used for the estimation of the curvature in all of the cases when the set of the focuses shows invariance under some isometries. This observation yields the general result for the approximation with not necessarily circumscribed polyellipses. If the Hausdorff distance is ε then, by the convexity, the approximating polyellipse must be between the outer and inner ε-parallel bodies of the triangle T. Then we can apply the previous estimation to the curvature of the polyellipse as a circumscribed curve of the inner parallel body. A continuity-type argumentation gives the contradiction.

Figure 78: A continuity-type argumentation.

Excercise 11.3.4 How to generalize Erdős-Vincze's theorem for regular polygons with vertices more than three.

12. fejezet - Rådström's embedding theorem

12.1 Rådström's embedding theorem

Let C* be the collection of non-empty bounded and closed (i.e. compact) convex sets in the coordinate space of dimension n equipped with the Hausdorff distance. In section 1.5 we proved that it is a metric space and the elements of C* form a cancellative semigroup with respect to the addition of sets. Moreover scalar multiplication have several properties like the ordinary scalar multiplication of vectors but not without any restriction (see section 1.4). Rådström's embedding theorem eliminates these additional requirements to provide an infinitely dimensional normed linear space environment for convex sets. The method can be used in general to present any cancellative semigroup as a subset of a group in the usual sense.

Definition Consider the set of ordered pairs (A, B) of elements in C*. We say that (A,B) and (C,D) are related if

(12.1)

Lemma 12.1.1 Relation 12.1 is an equivalence relation.

Proof Reflexivity and symmetry are clear by the definition. Suppose that (A,B) is related to (C,D) and (C,D) is related to (E,F). Then, by definition,

Adding these equations we have that

which means by the cancellation law 1.4.3 that

proving that (A,B) is related to (E,F) and the transitivity holds for 12.1 as was to be proved. ▮

The equivalence class represented by the ordered pair (A,B) will be denoted as [A,B].

Definition Let us define the addition

(12.2)

between the equivalence classes.

Excercise 12.1.2 Prove that the addition 12.2 is independent of the choice of the representation of equivalence classes. Find the zero element with respect to the operation 12.2 and prove that the set of the equivalence classes equipped with 12.2 is an Abelian group.

Definition Let the scalar multiplication be defined as

(12.3)

Excercise 12.1.3 Prove that the scalar multiplication 12.3 is independent of the choice of the representation of equivalence classes.

Lemma 12.1.4 The salar multiplication 12.3 satisfies the following properties:

(12.4)

(12.5)

(12.6)

and

(12.7)

Proof Suppose first of all that the scalar multiplier is non-negative in property 12.4. Then the left hand side can be written as

and the right hand side is

They are obviously equal to each other by property 1.24. The case of negative multipliers is similar. Property 12.5 comes from 1.25 in case of scalars with the same sign. The only non-trivial case when we have scalars with different signs. From now on we suppose that

(12.8)

Let the sum of the scalars be non-negative, i.e.

Then the left hand side of 12.5

The right hand side

To prove that they are the same we should check that

where

Since the scalars

have the same sign we can write that

and

as was to be proved. The discussion of the further possible cases is similar. To prove the associativity-like property 12.6 consider again the case of scalars with different signs under the convention 12.8. The left hand side is

The right hand side is

They are obviously equal to each other by property 1.26. Consider the case of scalars with the same sign. Then the left hand side preserves the ordering of the set A and B. The right hand side also preserves this ordering by changing it two times in case of negative scalar multipliers. The last property 12.7 is trivial.

Corollary 12.1.5 The set of equivalence classes is a real vector space with respect to the addition 12.2 and the scalar multiplication 12.3.

In what follows we shall construct a norm on the vector space of the equivalence classes.

Definition Let the mapping H be defined as

(12.9)

Lemma 12.1.6 Definition 12.9 is independent of the representation of equivalence classes.

Proof We have that

because the Hausdorff metric is translation invariant. Furthermore

provided that

i.e. [A,B] is related to [A',B'], and [C,D] is related to [C',D']. Therefore

as was to be proved.

Lemma 12.1.7 H is a translation invariant metric on the vector space of equivalence classes and

(12.10)

Proof The translation invariance follows from the corresponding theorem 1.5.5 for the Hausdorff distance:

On the other hand if we have a non-negative scalar multiplier then

The case of a negative scalar multiplier is similar. Among the metric properties non-negativity and symmetry are trivial because of the corresponding properties of the Hausdorff metric. To check the positive definiteness suppose that

which means that

because of the positive definiteness of the Hausdorff metric. This means that (A,B) and (C,D) are related to each other, i.e. the equivalence classes represented by them coincide. Finally, the triangle inequality follows as

because of the corresponding property of the Hausdorff metric.

Lemma 12.1.8 If δ is a translation invariant metric satisfying property 12.10 then

(12.11)

is a norm on the vector space.

Proof Suppose that y - x=y' - x'; then y+x'=y'+x=w and the translation invariance of the metric implies that

Therefore the mapping N is well-defined. The properties of the norm can be derived from the corresponding properties of the distance and property 12.10 (cf. absolute homogenity). To prove the triangle inequality consider two elements v=y - x and w=y' - x'. We have that

as was to be proved.

Corollary 12.1.9 The set of equivalence classes equipped with the norm coming from H forms a normed vector space.

Theorem 12.1.10 The family of non-empty compact convex subsets in the coordinate space of dimension n can be isometrically embedded as a convex cone into a real normed vector space. Explicitly

(12.12)

where the mapping 12.12 is additive and positively homogeneous in the sense that

for any positive real number λ.

Proof First of all note that for any non-empty compact convex sets L and M

(12.13)

because of L+(K+M)=M+(K+L). Especially,

Then we have

because of 12.13. Using the invariance property 12.13 again

provided that the scalar multiplier is positive (or at least non-negative). In the next step we prove that μ is an isometric embedding.

because of the translation invariance of the Hausdorff metric. ▮

Remark A similar statement can be formulated for any subfamily of non-empty compact convex sets provided that the subfamily is a cone: it is closed under the addition and the scalar multiplication by positive real numbers.

Excercise 12.1.11 Prove that the family of closed disks around the origin is closed under the addition and the scalar multiplication by positive real numbers.

For a more general survey of spaces of convex sets (together with the partial ordering induced by the inclusion of sets) we can refer to [17].

13. fejezet - Acknowledgement

Supported by TÁMOP-4.1.2.A/1-11/1.

14. fejezet - References

[1] M. Aigner and G. M. Ziegler, Proofs from the Book, 3rd. ed., Springer, 2004.

[2] H. Alzer and S. L. Qui, Monotonicity theorems and inequalities for the complete elliptic integrals, J. Comput. Appl. Math. 172 (2004), 289-312.

[3] K. Baron, J. Matkowski and K. Nikodem, A sandwich with convexity, Math. Pannon. 5, 1 Issue (1994), 139-144.

[4] I. Bárány, A generalization of Carathéodory's theorem, Discrete Math. 40 (1982), 141-152.

[5] I. Bárány and J. Matousek, Qudratically Many Colorful Simplices, SIAM Journal Discrete Math. 21 (1) (2007), 191-198.

[6] T. Bérczy, Konvex háromszögtestek, Középiskolai Matematikai Lapok 67 (3-4) 1983, 104-107.

[7] M. Berger, Geometry Revealed: A Jacob's Ladder to Modern Higher Geometry, Springer, 2010.

[8] G. Bianchi, A. Colestani and C. Pucci, On the second differentiablity of convex surfaces, Geometriae Dedicata Vol. 60, Number 1 (1996), 39-48.

[9] N. A. Bobylev, The Helly theorem for star-shaped sets, J. Math. Sci. 105 (2001), 1819-1825.

[10] T. Bonnesen and W. Fenchel, Theory of Convex Bodies, BCS Associates (Moscow, U. S.) ( 1987), translated by L. Boron, C. Christienson and B. Smith of Theory der Konvexen Körper, Springer, 1934.

[11] A. Borel, Some remarks about Lie groups transitive on spheres and tori, Bull. Amer. Math. Soc. Vol. 55, No. 6 (1949), 580-587.

[12] A. Borel, Le plan projectif des octaves et les sphéres comme espaces homogénes, C. R. Acad. Sci.Paris 230 (1950), 1378-1380.

[13] J. M. Borwein and A. S. Lewis, Convex Analysis and NonlinearOptimization, 2nd. ed., Springer 2006.

[14] T. Botts, Convex Sets, Amer. Math. Monthly 49 (1942), 527-535.

[15] M. Breen, The dimension of the kernel in an intersection of star-shaped sets, Arch. Math. 81 (2003), 485-490.

[16] M. Breen, The dimension of the kernel in finite and infinite intersections of star-shaped sets, Aequationes Math. 67 (2004), 263-275.

[17] W. A. Coppel, Foundations of Convex geometry, Cambridge University Press, 1998.

[18] H. S. M. Coxeter, Regular Polytopes, Dover Publication, Inc., 1973.

[19] A. A. Danielyan, On a polynomial approximation problem, J. Approx. Theory, Vol. 162, Issue 4, (April 2010), pp. 717-722.

[20] L. Danzer, B. Günbaumand V. Klee, Helly's theorem and its relatives, Proc. Sympos. Pure Math. 7, 101-188, Amer. Math. Soc. Providence, RI (1963).

[21] S. L. Devadoss and J. O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011.

[22] J. Eckhoff, Helly, Radon, and Carathéodory type theorems, Handbook of Convex Geometry Vol. A, P. M. Gruber and J. M. Wills, eds., 389-448, New York (1993).

[23] P. Erdős, F. Herzog and G. Piranian, Metric properties of polynomials, J. d'Analyse Mathématique, Vol. 6, No. 1 (1958), 125-148.

[24] P. Erdős and I. Vincze, On the approximation of closed convex plane curves, Mat. Lapok 9 (1958), 19-36 (in Hungarian, summaries in Russian and German).

[25] P. Erdős and I. Vincze, On the approximation of closed convex plane curves, J. Appl. Probab. 19 A (1982), 89-96.

[26] R. J. Gardner, Geometric Tomography, 2nd ed.Cambridge University Press, 2006.

[27] R. J. Gardner, The Brunn-Minkowski inequality, Bull. of Amer. Math. Soc., Vol. 39, no. 3, 355-405.

[28] T. Gharibyan, W. Luh and J. Müller, A lacunary version of Mergelian's approximation theorem, J. Approx. Theory, Vol. 162, Issue 4, (April, 2010), pp. 709-716.

[29] A. Gray and P. Green, Sphere transitive structures and triality authomorphisms, Pac.J. of Math. Vol. 34, No. 1 (1970), 83-96.

[30] C. Gross and T.-K. Strempel, On generalizations of conics and on a generalization of the Fermat-Toricelli problem, Amer. Math. Monthly 105, no. 8 (1998) 732-743.

[31] S. Guernon and R. Tessler, The Fermat-Steiner problem, Amer. Math. Monthly 109, Vol. 5 (2002), 443-451.

[32] R. Hartshorne, Euclid and Beyond, Springer, 2000.

[33] J. Kincses, The determination of a convex set from its angle function, Discrete Comput. Geom. 30 (2003), 287-297.

[34] J. Kincses and Á. Kurusa, Can you recognize the shape of a figure from its shadow?, Beiträge Algebra Geom. 36 (1) (1995), 25-35.

[35] V. Klee, The structure of semispaces, Math. Scand. 4 (1956), 54-64.

[36] V. Klee, The critical set of a convex body, Amer. J. Math. Vol. 75, No. 1 (1953), 178-188.

[37] S. R. Lay, Convex Sets and Their Applications, John Wiley & Sons, Inc., 1982.

[38] J.M. Lee, Introduction to Smooth Manifolds, Springer, 2003.

[39] G. G. Magaril-Il'yaev and V. M. Tikhomirov, Convex Analysis: Theory and Applications, American Mathematical Society, 2003.

[40] H. Martini and W. Wenzel, An analogue of the Krein-Milman theorem for star-shaped sets, Beiträge zur Algebra and Geometrie Vol. 44, No. 2 (2003), 441-449.

[41] Z. A. Melzak and J. S. Forsyth, Polyconics 1. Polyellipses and optimization, Quart. Appl. Math. 35, Vol. 2(1977), 239-255.

[42] S. N. Mergelyan, Uniform approximation to functions of a complex variable, Ser. and Approx. 3, Amer. Math.Soc. (1962) pp. 294-391.

[43] D. Montgomery and H. Samelson, Transformation groups of spheres, Ann. of Math., Vol 44, No.3 (1943), 454-470.

[44] K. Nikodem and S. Wasowicz, A sandwich theorem and Hyers-Ulam stability of affine functions, Aequationes Math. 49 (1995), 160-164.

[45] J. C. A. Paiva and A. Thompson, On the Perimeter and Area of the Unit Disk, Amer. Math. Monthly 112 (2005), 141-154.

[46] Zs. Páles and M. Bessenyei, Separation by linear interpolation families, J. Nonlinear and Convex Anal. Vol. 13, Number 1 (2012), 1-8.

[47] M. Ponce and P. Santibanez, On equidistant sets and generalized conics: the old and the new, Amer. Math. Monthly, in appear.

[48] H. Rådström, An embedding theorem for spaces of convex sets, Proc. Amer. Math. Soc. , Vol. 3, No. 1 (February, 1952), 165-169.

[49] K. C. Richards, Sharp power mean bounds for the Gaussian hypergeometric function, J. Math. Anal. Appl. 308 (2005), 303-313.

[50] A. W. Roberts and D. E. Varberg, Convex functions, Academic Press, Inc., 1973.

[51] J. Roe, Elementary Geometry, Oxford University Press, 1993.

[52] R. Schneider, Convex bodies: The Brunn-Minkowski Theory, Cambridge University Press, 1993.

[53] A. C. Thompson, Minkowski Geometry, Cambridge University Press, 1996.

[54] T. F. Tokieda, Mechanical ideas in Geometry, Amer. Math. Monthly, Vol. 105 No. 8 (Oct. 1998), 697-703.

[55] F. A. Valentine, Convex Sets,New York, 1964.

[56] Cs. Vincze and Á. Nagy, Examples and notes on generalized conics and their applications, AMAPN Vol. 26 (2010), 359-575.

[57] Cs. Vincze and Á. Nagy, An introduction to the theory of generalized conics and their applications, Journal of Geom. and Phys. Vol. 61 (2011), 815-828.

[58] Cs. Vincze and Á. Nagy, On the theory of generalized conics with applications in geometric tomography, J. Approx. Theory 164 (2012), 371-390.

[59] Cs. Vincze and Á. Nagy, On the localization of hv-convex compact planar sets given by their coordinate X-ray functions, arxiv:1303.4412.

[60] Cs. Vincze and A. Varga, On a lower and upper bound for the curvature of ellipses with more than two foci, Expo.Math. 26 (2008), 55-77.

[61] D. Watson, A refinement of theorems of Kirchberger and Carathéodory, J. of the Australian Math Soc. 15 (1973), 190-192.

[62] H. C. Wang, Finsler spaces with completely integrable equations of Killing, J. London Math. Soc. 22 (1947), 5-9.

[63] E. Weiszfeld, Sur le point pour lequel la somme distances de n points donnés est minimum, Tohoku Math. J. Sendai 43, Part II (1937), 355-386.

Notes

[1] In opposite case the complements of B(k)'s form an open cover of the space, especially, they form an open cover of B(1). Choosing a finite subcover and taking the complement again we have that the intersection of a finite subfamily of sets B(k)'s is in the complement of B(1). At the same time it is a subset in B(1) which is obviously a contradiction.

[2] Affine subspaces mean translates of linear subspaces, see also section 1.3

[3] The relative boundary of 2.10 means its boundary in its affine hull.

[4] Taking the sum of the coordinates is a linear operator and thus the sum of the coordinates in a linear combination is the linear combination of the sum of the coordinates.

[5] If t is less than 60 then the vertex is the foot of the perpendicular line from A to the corresponding tangent line 4.5. As they are rotating into the clockwise direction the path of the vertex will be the pedal curve of the arc AC with respect to A. In other words the lower line is not tangential to the full circle belonging to the lower arc AB under the critical value of the parameter.

[6] Hungarian translation: p megfigyelési pontja q-nak

[7] If H would bound the interior of K then it would support K at the same time. The existence of interior points in both sides of H causes an (n - 1)-dimensional intersection.

[8] Hungarian translation: k pontra feszíthető.

[9] It is clear that one of the sets A and B is non-empty; if (for example) A is the empty set the separation means the choice of a point not in the convex hull of B.

[10] Steinitz's comparison lemma states that if we have two polygons A(1)A(2) ... A(n) and B(1)B(2) ... B(n) in the plane such that the sides A(i)A(i+1) and B(i)B(i+1) are equal for i=1, 2, ..., n - 1 but the angles of the first polygon are less than or equal to the angles of the second polygon with at least one strict inequality then A(1)A(n) < B(1)B(n). The proof is based on the induction with respect to the number of vertices. All of Euclidean axioms are working except the parallel postulate. Therefore the lemma holds in spherical geometry too. Consider now a vertex figure and suppose in contrary that the sign changes at most two times (the number of changes of sign is obviously even including zero change too). If we have exactly two changes then there is a diagonal cutting the spherical polygon into two parts. One of them contains only - vertices and the other only + vertices. Applying the spherical version of Steinitz's comparison lemma to the - side we obtain that the diagonal is greater than the corresponding diagonal in the vertex figure belonging to the second polyhedron. Using the other side we have just the opposite conclusion which is impossible.

[11] As explicite examples we can consider curves, surfaces or compact domains in the space.

[12] In case of differentiable manifolds with Riemannian structures the subgroup H is the holonomy group of the Lévi-Civita connection and the alternative geometry is called Finsler geometry: instead of the Euclidean spheres in the tangent spaces, the unit vectors form the boundary of general convex sets containing the origin in their interiors (M. Berger).

[13] The only trivial orbit is that of the origin -- it is a singleton.

[14] For a more precise formulation of determination, verification and successive determination see [26]

[15] The Hausdorff distance of sets is determined by the distances between their points and, because of the invariance of T under H, the possible distances between the points of the boundary of Γ and T are the same as the possible distances between the points of E and T.