On the computer generation of random convex hulls

AbstractThe convex hull of X1,…,Xn, a sample of independent identically distributed Rd-valued random vectors with density f is called a random convex hull with parameters f and n. In this paper, we give an algorithm for the computer generation of random convex hulls when f is radial, i.e. when f(x)=g(‖x‖) for some function g. Then we look at the average time E(T) of the algorithm under a convenient computational mode. We consider only d=2.We show that for any f, our algorithm takes average time ω(log n). This lower bound is achieved for all radial densities with a polynomially decreasing tail. For the radial densities with an exponentially decreasing tail, we show that E(T)=0(log3/2n). Finally, for the uniform density on the unit circle, we have E(T)=0(n13log23n). This rate is also shown to be optimal for this density