Mathematics of Computation

Author(s): Josef Leydold; Wolfgang Hörmann.
Journal: Math. Comp. 67 (1998), 1617-1635.
MSC (1991): Primary 65C10; Secondary 65C05, 68U20
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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

-concave multivariate distributions by means of transformed density rejection.

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 , 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

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

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 -
Address at time of publication: Bogaziçi University, Department of Industrial Engineering, 80815 Bebek-Istanbul, Turkey
Email: whoer@statrix2.wu-wien.ac.at

DOI: 10.1090/S0025-5718-98-01004-7
PII: S 0025-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
Copyright of article: Copyright 1998, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS