Area and Perimeter of the Convex Hull of Stochastic Points
Pablo Pérez-Lantero · The Computer Journal · 2016
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 | $ \varepsilon \in (0,1)$ | , we provide an algorithm that runs in | $O(n^{6}/ \varepsilon )$ | 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- \varepsilon )w$ | . For the perimeter, we show a similar algorithm running in | $O(n^{6}/ \varepsilon )$ | time. Finally, given | $ \varepsilon ,\delta \in (0,1)$ | and for any measure, we show an | $O(n\log n+ (n/ \varepsilon ^2)\log (1/\delta ))$ | -time Monte Carlo algorithm that returns a value that, with probability of success at least | $1-\delta $ | , differs at most | $ \varepsilon $ | from the probability that the measure is at least | $w$ | .