#### Preview

Given a set [math] of [math] 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 [math] of [math] . The random subset [math] is formed by drawing each point [math] of [math] independently with a given rational probability [math] . 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 [math] . For [math] , we provide an algorithm that runs in [math] time and returns a value that is between the probability that the area is at least [math] , and the probability that the area is at least [math] . For the perimeter, we show a similar algorithm running in [math] time. Finally, given [math] and for any measure, we show an [math] -time Monte Carlo algorithm that returns a value that, with probability of success at least [math] , differs at most [math] from the probability that the measure is at least [math] .

*Keywords: *
probabilistic point sets;
convex hull;
area;
perimeter;
distribution function;
approximation

*Journal Article.*
*7199 words.*
*Illustrated.*

*Subjects: *
Computer Science

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or login to access all content.