Affordable Access

Random polytopes: Their definition, generation and aggregate properties

Mathematical Programming
Publication Date
  • Mathematics


The definition of random polytope adopted in this paper restricts consideration to those probability measures satisfying two properties. First, the measure must induce an absolutely continuous distribution over the positions of the bounding hyperplanes of the random polytope; and second, it must result in every point in the space being equally as likely as any other point of lying within the random polytope. An efficient Monte Carlo method for their computer generation is presented together with analytical formulas characterizing their aggregate properties. In particular, it is shown that the expected number of extreme points for such random polytopes increases monotonically in the number of constraints to the limiting case of a polytope topologically equivalent to a hypercube. The implied upper bound of 2 n where n is the dimensionality of the space is significantly less than McMullen's attainable bound on the maximal number of vertices even for a moderate number of constraints.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

Random half-integral polytopes

on Operations Research Letters Jan 01, 2011

On the variance of random polytopes

on Advances in Mathematics Jan 01, 2010

Random inscribing polytopes

on European Journal of Combinator... Jan 01, 2007

A highly efficient algorithm for the generation of...

on Physica D Nonlinear Phenomena Jan 01, 2010
More articles like this..