Abstract
Given a set of 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 of . The random subset is formed by drawing each point of independently with a given rational probability . 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 . For , we provide an algorithm that runs in time and returns a value that is between the probability that the area is at least , and the probability that the area is at least . For the perimeter, we show a similar algorithm running in time. Finally, given and for any measure, we show an -time Monte Carlo algorithm that returns a value that, with probability of success at least , differs at most from the probability that the measure is at least .
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.