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
MathSciNet review: 1604399
Full-text PDF Free Access

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. David Avis and Komei Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom. 8 (1992), no. 3, 295–313. ACM Symposium on Computational Geometry (North Conway, NH, 1991). MR 1174359, 10.1007/BF02293050
  • 3. Marcel Berger, Géométrie. Vol. 3, CEDIC, Paris; Nathan Information, Paris, 1977 (French). Convexes et polytopes, polyèdres réguliers, aires et volumes. [Convexes and polytopes, regular polyhedra, areas and volumes]. MR 536872
  • 4. H. Bieri and W. Nef, A recursive sweep-plane algorithm, determining all cells of a finite division of 𝑅^{𝑑}, Computing 28 (1982), no. 3, 189–198 (English, with German summary). MR 658182, 10.1007/BF02241747
  • 5. H. Bieri and W. Nef, A sweep-plane algorithm for computing the volume of polyhedra represented in Boolean form, Linear Algebra Appl. 52/53 (1983), 69–97 (English, with German summary). MR 709345, 10.1016/0024-3795(83)80008-1
  • 6. Th. Christof, Porta - a polyhedron representation transformation, Universität Heidelberg, code available at ftp://elib.zib-berlin.de/pub/mathprog.
  • 7. John Dagpunar, Principles of random variate generation, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1988. MR 968438
  • 8. Luc Devroye, Nonuniform random variate generation, Springer-Verlag, New York, 1986. MR 836973
  • 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 961051, 10.1137/0217060
  • 10. Ali Mili, Jules Desharnais, and Fatma Mili, Relational heuristics for the design of deterministic programs, Acta Inform. 24 (1987), no. 3, 239–276. MR 894556, 10.1007/BF00265990
  • 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. Ryzhik, Table of integrals, series, and products, Fourth edition prepared by Ju. V. Geronimus and M. Ju. Ceĭtlin. Translated from the Russian by Scripta Technica, Inc. Translation edited by Alan Jeffrey, Academic Press, New York-London, 1965. MR 0197789
  • 14. Peter Gritzmann and Victor Klee, On the complexity of some basic problems in computational convexity. II. Volume and mixed volumes, Polytopes: abstract, convex and computational (Scarborough, ON, 1993), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 440, Kluwer Acad. Publ., Dordrecht, 1994, pp. 373–466. MR 1322071
  • 15. Branko Grünbaum, Convex polytopes, With the cooperation of Victor Klee, M. A. Perles and G. C. Shephard. Pure and Applied Mathematics, Vol. 16, Interscience Publishers John Wiley & Sons, Inc., New York, 1967. MR 0226496
  • 16. H. Hadwiger, Eulers Charakteristik und kombinatorische Geometrie, J. Reine Angew. Math. 194 (1955), 101–110 (German). MR 0073221
  • 17. H. Hadwiger, Eine Schnittrekursion für die Eulersche Charakteristik euklidischer Polyeder mit Anwendungen innerhalb der kombinatorischen Geometrie, Elem. Math. 23 (1968), 121–132 (German). MR 0236818
  • 18. Wolfgang Hörmann, A rejection technique for sampling from 𝑇-concave distributions, ACM Trans. Math. Software 21 (1995), no. 2, 182–193. MR 1342355, 10.1145/203082.203089
  • 19. W. Hörmann, A universal generator for discrete log-concave distributions, Computing 52 (1994), no. 1, 89–96 (English, with English and German summaries). MR 1259422, 10.1007/BF02243398
  • 20. R. Dutter and W. Grossmann (eds.), COMPSTAT 1994, Physica-Verlag, Heidelberg, 1994. MR 1321146
  • 21. M. E. Johnson, Multivariate statistical simulation, John Wiley & Sons, New York, 1987.
  • 22. Jim Lawrence, Polytope volume computation, Math. Comp. 57 (1991), no. 195, 259–271. MR 1079024, 10.1090/S0025-5718-1991-1079024-2
  • 23. P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179–184. MR 0283691
  • 24. T. S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall, The double description method, Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, Princeton University Press, Princeton, N. J., 1953, pp. 51–73. MR 0060202
  • 25. Walter Nef, Beiträge zur Theorie der Polyeder, Herbert Lang, Bern, 1978 (German). Mit Anwendungen in der Computergraphik; Beiträge zur Mathematik, Informatik und Nachrichtentechnik, Band 1. MR 0500548
  • 26. András Prékopa, On logarithmic concave measures and functions, Acta Sci. Math. (Szeged) 34 (1973), 335–343. MR 0404557
  • 27. G. C. Shephard, An elementary proof of Gram’s theorem for convex polytopes, Canad. J. Math. 19 (1967), 1214–1217. MR 0225228
  • 28. Ş. Ştefănescu and I. Văduva, On computer generation of random vectors by transformations of uniformly distributed vectors, Computing 39 (1987), no. 2, 141–153 (English, with German summary). MR 919664, 10.1007/BF02310103
  • 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ünter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028

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