A sweep-plane algorithm for generating random tuples in simple polytopes
Open Access
- 1 October 1998
- journal article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 67 (224) , 1617-1635
- https://doi.org/10.1090/s0025-5718-98-01004-7
Abstract
A sweep-plane algorithm of Lawrence for convex polytope computation is adapted to generate random tuples on simple polytopes. In our method an affine hyperplane is swept through the given polytope until a random fraction (sampled from a proper univariate distribution) of the volume of the polytope is covered. Then the intersection of the plane with the polytope is a simple polytope with smaller dimension. In the second part we apply this method to construct a black-box algorithm for log-concave and T T -concave multivariate distributions by means of transformed density rejection.Keywords
This publication has 19 references indexed in Scilit:
- A rejection technique for sampling from T -concave distributionsACM Transactions on Mathematical Software, 1995
- Adaptive Rejection Sampling for Gibbs SamplingJournal of the Royal Statistical Society Series C: Applied Statistics, 1992
- Efficient generation of random variates via the ratio-of-uniforms methodStatistics and Computing, 1991
- Polytope Volume ComputationMathematics of Computation, 1991
- A sweep-plane algorithm for computing the volume of polyhedra represented in boolean formLinear Algebra and its Applications, 1983
- The maximum numbers of faces of a convex polytopeMathematika, 1970
- An Elementary Proof of Gram's Theorem for Convex PolytopesCanadian Journal of Mathematics, 1967
- Eulers Charakteristik und kombinatorische Geometrie.Journal für die reine und angewandte Mathematik (Crelles Journal), 1955
- Maximal Orders in Rational Cyclic Algebras of Composite DegreeTransactions of the American Mathematical Society, 1939
- Steinitz Field Towers for Modular FieldsTransactions of the American Mathematical Society, 1939