A sweep-plane algorithm for generating random tuples in simple polytopes
Mathematics of ComputationPublished 1 January 1998Open access
Josef Leydold, Wolfgang Hörmann
Citations30
SJR quartileQ1
SJR score1.84
SNIP1.96
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A sweep-plane algorithm by Lawrence for convex polytope computation is adapted to generate random tuples on simple polytopes and is applied to construct a black-box algorithm for log-concave and T- Concave multivariate distributions by means of transformed density rejection.
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 T -concave multivariate distributions by means of transformed density rejection.
Keywords
Computer ScienceMathematics
American Mathematical MonthlyAlgorithms in Combinatorial Geometry.
1,801 Citations1989Jacob E. Goodman, Herbert Edelsbrunner
Journal of the Royal Statistical Society Series C (Applied Statistics)Adaptive Rejection Sampling for Gibbs Sampling
1,649 Citations1992Walter R. Gilks, Pascal Wild
The method is adaptive: as sampling proceeds, the rejection envelope and the squeezing function converge to the density function, and is intended for situations where evaluation of the density is computationally expensive.
Lectures on Polytopes Updated Seventh Printing of the First Edition
1,580 Citations1995Günter M. Ziegler
A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
477 Citations1991David Avis, Komei Fukuda
A new pivot-based algorithm which can be used with minor modification for the enumeration of the facets of the convex hull of a set of points, or for the listing of the vertices of an arrangement or of a convex polyhedron, in arbitrary dimension is presented.
Discrete & Computational GeometryA pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
403 Citations1992David Avis, Komei Fukuda
SIAM Journal on ComputingOn the Complexity of Computing the Volume of a Polyhedron
308 Citations1988Martin Dyer, Alan Frieze
It is shown that computing the volume of a polyhedron given either as a list of facets or as aList of vertices is as hard as computing the permanent of a matrix.
Mathematics of ComputationPolytope volume computation
199 Citations1991Jim Lawrence
A combinatorial form of Gram's relation for convex polytopes can be adapted for use in computing polytope volume and it is deduced that, when A and b have rational entries (so that the volume of P is also a rational number), the number of binary digits in the denominator of the volume cannot be bounded by a polynomial.
Birkhäuser Basel eBooksA Revised Implementation of the Reverse Search Vertex Enumeration Algorithm
186 Citations2000David Avis
Mathematics of ComputationPrinciples of Random Variate Generation
173 Citations1990H. N., J. S. Dagpunar
Transactions of the American Mathematical SocietySteinitz field towers for modular fields
151 Citations1939Saunders MacLane
Statistics and ComputingEfficient generation of random variates via the ratio-of-uniforms method
146 Citations1991J. C. Wakefield, Alan E. Gelfand +1 more
Transactions of the American Mathematical SocietyMaximal orders in rational cyclic algebras of composite degree
145 Citations1939Sam Perlis
ACM Transactions on Mathematical SoftwareA rejection technique for sampling from <i>T</i> -concave distributions
83 Citations1995Wolfgang Hörmann
A rejection algorithm that uses a new method for constructing simple hat functions for a unimodal, bounded density, is introduced called “transformed density rejection,” based on the idea of transforming f with a suitable transformation T such that T(f(x) is concave.
Canadian Journal of MathematicsAn Elementary Proof of Gram's Theorem for Convex Polytopes
53 Citations1967G. C. Shephard
Acta InformaticaRelational heuristics for the design of deterministic programs
47 Citations1987Ali Mili, Jules Desharnais +1 more
This paper formulate some heuristic solutions to relational equations and shows that the design of deterministic programs can be formulated as the resolution of relational equations.
ComputingA universal generator for discrete log-concave distributions
24 Citations1994Wolfgang Hörmann
An algorithm that can be used to sample from any discrete log-concave distribution (e.g. the binomial and hypergeometric distributions) based on rejection from a discrete dominating distribution that consists of parts of the geometric distribution is given.
ComputingA recursive sweep-plane algorithm, determining all cells of a finite division of Rd
23 Citations1982Hanspeter Bieri, Walter Nef
An algorithm of this kind that enumerates the cells of all dimensions into whichRd is partitioned by a finite set of hyperplanesFi0, which allows the construction of an algorithm recursive with respect to the dimension of space.
Linear Algebra and its ApplicationsA sweep-plane algorithm for computing the volume of polyhedra represented in boolean form
22 Citations1983Hanspeter Bieri, Walter Nef
It is shown that V(P) is determined by the local properties of P at all its vertices, and an algorithm polvol is presented for the computation of the d-dimensional volume V( P) of a bounded polyhedron P ⊂ R d.
ComputingOn computer generation of random vectors by transformations of uniformly distributed vectors
14 Citations1987Stefan Corneliu V. Stefanescu, Ion Văduva
A general method of computer generation of random vectors based on transformations of uniformly distributed vectors is discussed, then applied to build up efficient algorithms for generatingq-exponential random vectors and multivariate normal ort-distributed vectors.
COMPSTATUniversal Generators for Correlation Induction
10 Citations1994Wolfgang Hörmann, Gerhard Derflinger
It is shown that transformed density rejection is well suited to construct universal algorithms suitable for correlation induction which is important for variance reduction in simulation.