10. Remarks 39
Remark: This number is way too big. In practice, after performing each one-
step projection
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.
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
is a polyhedron, is called the algebra of polyhedra and denoted
1. Let T :
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
such that (α1f1 + α2f2) g = α1(f1 g) + α2(f2 g) for
any f1,f2,g
and such that [P1] [P2] = [P1 + P2] for any two polyhedra
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
Previous Page Next Page