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].
Previous Page Next Page