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

From MaRDI portal





The generation of uniformly distributed random points on an \(n\)-polytope is studied using a sweep plane technique. The affine hyperplane is swept through a given polytope until a random fraction of the volume of the polytope is covered. The intersection of the plane with the polytope is a simple polytope with smaller dimension. By recursion one arrives at a polytope of dimension \(0\), that is a single point. The sweep-plane algorithm for simple polytopes and a rejection technique for multivariate log-concave densities are described. The algorithm also works for non-convex polytopes. The complexity of the generation procedure does not grow as fast with the dimension as by other methods. A black-box algorithm for the log-concave and \(T\)-concave multivariate distributions by following the idea of transformed density rejection is also constructed.



Cites work



Describes a project that uses

Uses Software






This page was built for publication: A sweep-plane algorithm for generating random tuples in simple polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210961)