10. Remarks 39

Remark: This number is way too big. In practice, after performing each one-

step projection

Rd

−→

Rd−1,

it is advisable to “clean” the list of obtained inequal-

ities by removing those that can be removed without changing the image of the

projection. Still, typically the number of inequalities needed to describe the pro-

jection is substantially larger than the number of inequalities needed to describe

the original polyhedron.

2◦.

Prove that the Minkowski sum P1 +P2 of two polyhedra in Euclidean space

is a polyhedron.

We define an important subalgebra of the algebra of closed convex sets from

Definition 7.3.

(9.3) Definition. The real vector space spanned by the indicator functions [P ],

where P ⊂

Rd

is a polyhedron, is called the algebra of polyhedra and denoted

P(Rd).

PROBLEMS.

1. Let T :

Rn

−→

Rm

be a linear transformation. Prove that there exists

a linear transformation T : P(Rn) −→ P(Rm) such that T [P ] = [T (P )] for all

polyhedra P ⊂ Rn.

Hint: Cf. Theorem 8.1.

2. Prove that there exists a commutative and associative operation f g for

functions f, g ∈

P(Rd)

such that (α1f1 + α2f2) g = α1(f1 g) + α2(f2 g) for

any f1,f2,g ∈

P(Rd)

and such that [P1] [P2] = [P1 + P2] for any two polyhedra

P1,P2 ⊂

Rd

Hint: Cf. Problem 1 of Section 8.2.

10. Remarks

A general reference in convexity is [W94]. Our discussion of positive polynomi-

als in Section 3 follows [R95] and [R00] with some simplifications. A classical

reference for Helly’s Theorem and its numerous applications is [DG63]. More re-

cent developments, including applications of topological methods, are surveyed in

[E93], [K95], [We97] and [Z97]

ˇ

(see also references therein). See also [Bar82] for

a nice and elementary generalization of Radon’s Theorem and Helly’s Theorem and

[Mat02] for further results in this direction. For the Euler characteristic and valu-

ations, see [Kl63], [Mc93a] and [MS83]. Note that our definition of the relevant

algebras (the algebra of compact convex sets, the algebra of closed convex sets and

the algebra of polyhedra) may be different from those in [Mc93a], [MS83] and

elsewhere. Often, an equivalence relation of some kind is imposed and the algebra

is factored modulo that relation. The role of algebra multiplication is played by

the convolution operation (which we introduce in Problem 1 of Section 8.2 and

Problem 2 of Section 9.3).

Intrinsic volumes in the context of the general theory of valuations are discussed

in [KR97]. The Fourier-Motzkin elimination procedure is discussed in detail in

[Z95].