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

Leydold, Josef; Hörmann, Wolfgang

doi:10.1090/S0025-5718-98-01004-7

A sweep-plane algorithm for generating random tuples in simple polytopes
HTML articles powered by AMS MathViewer

by Josef Leydold and Wolfgang Hörmann PDF

Math. Comp. 67 (1998), 1617-1635 Request permission

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

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.
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, DOI 10.1007/BF02293050
Marcel Berger, Géométrie. Vol. 1, CEDIC, Paris; Nathan Information, Paris, 1977 (French). Actions de groupes, espaces affines et projectifs. [Actions of groups, affine and projective spaces]. MR 536870
H. Bieri and W. Nef, A recursive sweep-plane algorithm, determining all cells of a finite division of $\textbf {R}^{d}$, Computing 28 (1982), no. 3, 189–198 (English, with German summary). MR 658182, DOI 10.1007/BF02241747
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, DOI 10.1016/0024-3795(83)80008-1
Th. Christof, Porta – a polyhedron representation transformation, Universität Heidelberg, code available at ftp://elib.zib-berlin.de/pub/mathprog.
John Dagpunar, Principles of random variate generation, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1988. MR 968438
Luc Devroye, Nonuniform random variate generation, Springer-Verlag, New York, 1986. MR 836973, DOI 10.1007/978-1-4613-8643-8
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, DOI 10.1137/0217060
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, DOI 10.1007/BF00265990
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.
W. R. Gilks and P. Wild, Adaptive rejection sampling for Gibbs sampling, Appl. Statistics 41 (1992), 337–348.
I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products, Academic Press, New York-London, 1965. 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. MR 0197789
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
Branko Grünbaum, Convex polytopes, Pure and Applied Mathematics, Vol. 16, Interscience Publishers John Wiley & Sons, Inc., New York, 1967. With the cooperation of Victor Klee, M. A. Perles and G. C. Shephard. MR 0226496
Saunders MacLane, Steinitz field towers for modular fields, Trans. Amer. Math. Soc. 46 (1939), 23–45. MR 17, DOI 10.1090/S0002-9947-1939-0000017-3
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 236818
Wolfgang Hörmann, A rejection technique for sampling from $T$-concave distributions, ACM Trans. Math. Software 21 (1995), no. 2, 182–193. MR 1342355, DOI 10.1145/203082.203089
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, DOI 10.1007/BF02243398
R. Dutter and W. Grossmann (eds.), COMPSTAT 1994, Physica-Verlag, Heidelberg, 1994. MR 1321146
M. E. Johnson, Multivariate statistical simulation, John Wiley & Sons, New York, 1987.
Jim Lawrence, Polytope volume computation, Math. Comp. 57 (1991), no. 195, 259–271. MR 1079024, DOI 10.1090/S0025-5718-1991-1079024-2
P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179–184. MR 283691, DOI 10.1112/S0025579300002850
Sam Perlis, Maximal orders in rational cyclic algebras of composite degree, Trans. Amer. Math. Soc. 46 (1939), 82–96. MR 15, DOI 10.1090/S0002-9947-1939-0000015-X
Walter Nef, Beiträge zur Theorie der Polyeder, Beiträge zur Mathematik, Informatik und Nachrichtentechnik, Band 1, Herbert Lang, Bern, 1978 (German). Mit Anwendungen in der Computergraphik. MR 0500548
András Prékopa, On logarithmic concave measures and functions, Acta Sci. Math. (Szeged) 34 (1973), 335–343. MR 404557
G. C. Shephard, An elementary proof of Gram’s theorem for convex polytopes, Canadian J. Math. 19 (1967), 1214–1217. MR 225228, DOI 10.4153/CJM-1967-110-7
Ş. Ş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, DOI 10.1007/BF02310103
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.
Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1