Area and Perimeter of the Convex Hull of Stochastic Points

*Given a set P of n points in the plane, we study the computation of the probability distribution function of both the area and perimeter of the convex hull of a random subset S of P. The random subset S is formed by drawing each point p of P independently with a given rational probability pi(p). For both measures of the convex hull, we show that it is #P-hard to compute the probability that the measure is at least a given bound w. For epsilon is an element of(0, 1), we provide an algorithm that runs in O(n(6)/epsilon) time and returns a value that is between the probability that the area is at least w, and the probability that the area is at least (1 - epsilon) w. For the perimeter, we show a similar algorithm running in O(n(6)/epsilon) time. Finally, given epsilon, delta is an element of (0, 1) and for any measure, we show an O(n log n + (n/epsilon(2)) log(1/delta))-time Monte Carlo algorithm that returns a value that, with probability of success at least 1 - delta, differs at most epsilon from the probability that the measure is at least w.