Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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?)


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: http://dx.doi.org/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
Article copyright: © Copyright 1998 American Mathematical Society