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

 $convD\cap convE\ne \mathrm{\varnothing }.$

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

 $v\in {D}_{i}\cap {E}_{j}$

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

 $i+j=1+j\le 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\ge \mathrm{d}\mathrm{i}\mathrm{m}{\mathrm{\Gamma }}_{D}\cup {\mathrm{\Gamma }}_{E}=\mathrm{d}\mathrm{i}\mathrm{m}{\mathrm{\Gamma }}_{D}+\mathrm{d}\mathrm{i}\mathrm{m}{\mathrm{\Gamma }}_{E}=i-1+j-1=i+j-2$

showing that

 $i+j\le 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

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\in {D}_{i}\cap {E}_{j},$

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

 $v\in conv\left\{{p}_{1},\mathrm{\dots },{p}_{i}\right\}\cap conv\left\{{q}_{1},\mathrm{\dots },{q}_{j}\right\}$

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

 $T:=\left\{{p}_{1},\mathrm{\dots },{p}_{i},{q}_{1},\mathrm{\dots },{q}_{j}\right\}$

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

 $\sum _{{v}_{i}\in D}{\lambda }_{i}{v}_{i}=\sum _{{w}_{j}\in E}{\mu }_{j}{w}_{j}$

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).