CHAPTER 2

Definitions of Polyhedra, Their Faces and Cones

In this chapter, we define basic notions of polyhedra, faces and their dual faces.

2.1. Polyhedron

Definition 2.1. Let U ⊂ Rn be a subspace endowed with an inner product

, in Rn. Then V is called an aﬃne subspace in Rn if V = p + U for some p ∈ Rn.

Definition 2.2. Let V be an aﬃne subspace in

Rn.

A hyperplane in V is a

set

πq,r = {y ∈ V : q, y = r} where q ∈

Rn

and r ∈ R.

The corresponding closed upper half-space and lower half-space are

πq,r

+

= {y ∈ V : q, y ≥ r} and πq,r

−

= {y ∈ V : q, y ≤ r}.

The open upper half-space and lower half space are

(πq,r)◦ +

= {y ∈ V : q, y r} and

(πq,r)◦ −

= {y ∈ V : q, y r}.

Definition 2.3 (Polyhedron in V ). Let V be an aﬃne subspace in

Rn

and let

Π = {πqj

,rj

}j=1 N be a set of hyperplanes in V . A polyhedron P in V is defined to be

an intersection of closed upper half-spaces πqj +

,rj

:

P =

N

j=1

πqj

+

,rj

=

N

j=1

{y ∈ V : qj , y ≥ rj for 1 ≤ j ≤ N}.

We call the above collection Π = Π(P) the generator of P. We denote the polyhedron

P by P(Π) indicating its generator Π. Sometimes, we also mean the generator Π of

P to be the collection of normal vectors {qj}j=1 N instead of hyperplanes {πqj

,rj

}j=1.N

Example 2.1. A set of hyper-planes Π = {πqj

,rj

: 1 ≤ j ≤ 5} where qj =

1

2

(e1+

e2 + e3 −ej) −

1

3

(e1 + e2 + e3) with rj = 1/6 for j = 1, 2, 3 and qj = ±(e1 + e2 + e3)

with rj = ±1 for j = 4, 5 makes a triangle P(Π) = Ch(e1, e2, e3) (two dimensional

polyhedron) in R3.

5