Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

8. fejezet - Kirchberger's separation theorem

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

c o n v D c o n v E .

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

v D i E j

then i+j is at most n+2.

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

c o n v D = D n + 1   a n d   c o n v E = E n + 1 .

Therefore

i n + 1   a n d   j n + 1 .

(8.1)

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

i + j = 1 + j 1 + n + 1 = n + 2

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,

n d i m Γ D Γ E = d i m Γ D + d i m Γ E = i - 1 + j - 1 = i + j - 2

showing that

i + j n + 2

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

T D   a n d   T E

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,

v D i E j ,

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

v c o n v { p 1 , , p i } c o n v { q 1 , , q j }

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

T : = { p 1 , , p i , q 1 , , q j }

the intersections

T D   a n d   T E

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

T D   a n d   T E

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

v i D λ i v i = w j E μ j w j

under the additional conditions

λ i = 1   a n d   μ j = 1 .

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

i = 1 m ' λ i v i = j = 1 k ' μ j w j , λ i = 1   a n d   μ j = 1 .

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