Mathematika

Research Article

Few points to generate a random polytope

Imre Báránya1 and Leoni Dallaa2

a1 Mathematical Institute of the Hungarian Academy of Sciences, P.O. Box 127, 1364 Budapest, Hungary

a2 Mathematics Department, Athens University, Athens, 157-81, Greece.

Abstract

A random polytope, Kn, is the convex hull of n points chosen randomly, independently, and uniformly from a convex body It is shown here that, with high probability, Kn can be obtained by taking the convex hull of m = o(n) points chosen independently and uniformly from a small neighbourhood of the boundary of K.

(Received May 01 1996)

Key Words:

  • 52A22: CONVEX AND DISCRETE GEOMETRY: General Convexity; Random convex sets.