Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A sweep-plane algorithm for generating
random tuples in simple polytopes


Authors: Josef Leydold and Wolfgang Hörmann
Journal: Math. Comp. 67 (1998), 1617-1635
MSC (1991): Primary 65C10; Secondary 65C05, 68U20
DOI: https://doi.org/10.1090/S0025-5718-98-01004-7
MathSciNet review: 1604399
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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$-concave multivariate distributions by means of transformed density rejection.


References [Enhancements On Off] (What's this?)

  • 1. D. Avis, A C implementation of the reverse search vertex enumeration algorithm, Tech. report, School of Computer Science, McGill University, Montreal, Quebec, 1993, report and code available at ftp://mutt.cs.mcgill.ca/pub/C.
  • 2. D. Avis and K. Fukuda, A pivoting algorithm for convex hull and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom. 8 (1992), 295-313. MR 93h:68137
  • 3. M. Berger, Geometrie, 2 ed., vol. 3, Convexes et polytopes, polyedres reguliers, aires et volumes. Fernand Nathan, Paris, 1978. MR 81k:51001c
  • 4. H. Bieri and W. Nef, A recursive sweep-plane algorithm, determining all cells of a finite division of $R^m$, Computing 28 (1982), 189-198. MR 83k:52014
  • 5. -, A sweep-plane algorithm for the volume of polyhedra represented in boolean form, Linear Algebra Appl. 52/53 (1983), 69-97. MR 85h:52007
  • 6. Th. Christof, Porta - a polyhedron representation transformation, Universität Heidelberg, code available at ftp://elib.zib-berlin.de/pub/mathprog.
  • 7. J. Dagpunar, Principles of random variate generation, Clarendon Press, Oxford, 1988. MR 90d:65020
  • 8. L. Devroye, Nonuniform random variate generation, Springer-Verlag, New-York, 1986. MR 87i:65012
  • 9. M. E. Dyer and A. M. Frieze, On the complexity of computing the volume of a polyhedron, SIAM J. Comput. 17 (1988), no. 5, 967-974. MR 90f:68077
  • 10. H. Edelsbrunner, Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, 1987. MR 89a:68025
  • 11. K. Fukuda, cdd reference manual, Tech. report, ETH Zentrum, Zürich, Switzerland, 1995, report and code availeable at ftp://ifor13.ethz.ch/pub/fukuda/cdd.
  • 12. W. R. Gilks and P. Wild, Adaptive rejection sampling for Gibbs sampling, Appl. Statistics 41 (1992), 337-348.
  • 13. I. S. Gradshteyn and I. M. Ryzhnik, Table of integrals, series, and products, 5th ed., Academic Press, 1965. MR 33:5952
  • 14. P. Gritzmann and V. Klee, On the complexity of some basic problems in computational convexity. II: Volume and mixed volumes. Polytopes: abstract, convex and computational, (Scarborough, Ontario, Canada) (T. Bisztriczky et al., eds.), NATO ASI Series, Ser. C, Math. Phys. Sci., no. 440, NATO Advanced Study Institute, Kluwer Academic Publishers, 1994, pp. 373-466. MR 96k:52012
  • 15. B. Grünbaum, Convex polytopes, Interscience, 1967. MR 37:2085
  • 16. H. Hadwiger, Eulers Charakteristik und kombinatorische Geometrie, J. Reine Angew. Math. 194 (1955), 101-110. MR 17:402a
  • 17. -, Eine Schnittrekursion für die Eulersche Charakteristik euklidischer Polyeder, Elem. Math. 23 (1968), no. 6, 121-132. MR 38:5112
  • 18. W. Hörmann, A rejection technique for sampling from $T$-concave distributions, ACM Trans. Math. Software 21 (1995), no. 2, 182-193. MR 96b:65018
  • 19. -, A universal generator for bivariate log-concave distributions, Computing 52 (1994), 89-96. MR 94j:65014
  • 20. W. Hörmann and G. Derflinger, Universal generators for correlation induction, Compstat, Proceedings in Computational Statistics (Heidelberg) (R. Dutter and W. Grossmann, eds.), Physica-Verlag, 1994, pp. 52-57. MR 95j:62003
  • 21. M. E. Johnson, Multivariate statistical simulation, John Wiley & Sons, New York, 1987.
  • 22. J. Lawrence, Polytope volume computation, Math. Comput. 57 (1991), no. 195, 259-271. MR 91j:52019
  • 23. P. McMullen, The maximum number of faces of a convex polytope, Mathematika 17 (1970), 179-184. MR 44:921
  • 24. T. S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall, The double description method, Contribution to the Theory of Games, Vol. II (H. W. Kuhn and A. W. Tucker, eds.), Annals of Math. Studies, vol. 28, Princton University Press, 1953, pp. 81-103. MR 15:638g
  • 25. W. Nef, Beiträge zur Theorie der Polyeder, Herbert Lang, Bern, 1978. MR 58:18152
  • 26. A. Prékopa, On logarithmic concave measures and functions, Acta Sci. Math. Hungarica 34 (1973), 335-343. MR 53:8357
  • 27. G. C. Shephard, An elementary proof of Gram's theorem for convex polytopes, Canad. J. Math. 19 (1967), 1214-1217. MR 37:822
  • 28. S. Stefanescu and I. Vaduva, On computer generation of random vectors by transformations of uniformly distributed vectors, Computing 39 (1987), 141-153. MR 89i:65008
  • 29. J. C. Wakefield, A. E. Gelfand, and A. F. M. Smith, Efficient generation of random variates via the ratio-of-uniforms method, Statist. Comput. 1 (1991), 129-133.
  • 30. G. M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 96a:52011

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65C10, 65C05, 68U20

Retrieve articles in all journals with MSC (1991): 65C10, 65C05, 68U20


Additional Information

Josef Leydold
Affiliation: University of Economics and Business Administration, Department for Applied Statistics and Data Processing, Augasse 2-6, A-1090 Vienna, Austria
Email: Josef.Leydold@wu-wien.ac.at

Wolfgang Hörmann
Affiliation: University of Economics and Business Administration, Department for Applied Statistics and Data Processing, Augasse 2-6, A-1090 Vienna, Austria; University of Economics and Business Administration, Department for Applied Statistics and Data Processing, Augasse 2-6, A-1090 Vienna, Austria
Address at time of publication: Boğaziçi University, Department of Industrial Engineering, 80815 Bebek-Istanbul, Turkey
Email: whoer@statrix2.wu-wien.ac.at

DOI: https://doi.org/10.1090/S0025-5718-98-01004-7
Keywords: Uniform distributions, polytope, rejection method, multivariate log-concave distributions, universal method
Received by editor(s): February 26, 1997
Received by editor(s) in revised form: August 18, 1997
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society