Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

9. fejezet - Convex polytopes and polyhedra

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

q 1 , , q m .

(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

F 1 , , F m

(9.2)

be closed half-spaces bonded by the hyperplanes

A 1 , A m ,

(9.3)

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

K : = i = 1 m F i

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

K E n

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

e x t K e x t ( K A 1 ) e x t ( K A m ) .

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

L * : = { n E n | p L : n , p 1 } .

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

( L 1 L 2 ) * = L 1 * L 2 * ,

(9.4)

L 1 L 2 L 2 * L 1 *

(9.5)

λ > 0 : ( λ L ) * = 1 λ L * .

(9.6)

If K is a closed convex set containing the origin then

( K * ) * = K

(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

p , n 1

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

a 1 x 1 + a 2 x 2 + + a n x n = 1 .

(9.8)

Using the notation

n : = ( a 1 , , a n )

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

n , x = 1 .

(9.9)

Since the origin is in K the inequality

n , x < 1

(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

F i : = { n E n | n , q i 1 } ,

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

L i = 1 m F i

is obvious. On the other hand for any convex combination

q = λ 1 q 1 + + λ m q m

relations

n , q 1 1 , , n , q m 1

imply that

n , q = λ 1 n , q 1 + + λ m n , q m λ 1 + + λ m = 1

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

F i * : = { n * E n | n * , q i * 1 } ,

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.