Uniform decompositions of polytopes

Daniel Berend¹ ; Luba Bromberg²

¹ Departments of Mathematics and Computer Science Ben-Gurion University of the Negev Beer-Sheva 84105, Israel
² Department of Mathematics Ben-Gurion University of the Negev Beer-Sheva 84105, Israel

Applicationes Mathematicae, Tome 33 (2006) no. 2, pp. 243-252

Résumé

We design a method of decomposing convex polytopes into simpler polytopes. This decomposition yields a way of calculating exactly the volume of the polytope, or, more generally, multiple integrals over the polytope, which is equivalent to the way suggested in Schechter, based on Fourier–Motzkin elimination (Schrijver). Our method is applicable for finding uniform decompositions of certain natural families of polytopes. Moreover, this allows us to find algorithmically an analytic expression for the distribution function of a random variable of the form $\sum_{i=1}^{d}c_{i}X_{i}$, where $(X_{1},\ldots ,X_{d})$ is a random vector, uniformly distributed in a polytope.

Détail

DOI : 10.4064/am33-2-7

Mots-clés : design method decomposing convex polytopes simpler polytopes decomposition yields calculating exactly volume polytope generally multiple integrals polytope which equivalent suggested schechter based fourier motzkin elimination schrijver method applicable finding uniform decompositions certain natural families polytopes moreover allows algorithmically analytic expression distribution function random variable form sum where ldots random vector uniformly distributed polytope