text: 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 .
  @cite_0: We study the convex-hull problem in a probabilistic setting, motivated by the need to handle data uncertainty inherent in many applications, including sensor databases, location-based services and computer vision. In our framework, the uncertainty of each input site is described by a probability distribution over a finite number of possible locations including a location to account for non-existence of the point. Our results include both exact and approximation algorithms for computing the probability of a query point lying inside the convex hull of the input, time-space tradeoffs for the membership queries, a connection between Tukey depth and membership queries, as well as a new notion of @math -hull that may be a useful representation of uncertain hulls.
  @cite_17: Consider a set of points in d dimensions where the existence or the location of each point is determined by a probability distribution. The convex hull of this set is a random variable distributed over exponentially many choices. We are interested in finding the most likely convex hull, namely, the one with the maximum probability of occurrence. We investigate this problem under two natural models of uncertainty: the point (also called the tuple) model where each point (site) has a fixed position s i but only exists with some probability π i , for 0 < π i ≤ 1, and the multipoint model where each point has multiple possible locations or it may not appear at all. We show that the most likely hull under the point model can be computed in O(n 3) time for n points in d = 2 dimensions, but it is NP–hard for d ≥ 3 dimensions. On the other hand, we show that the problem is NP–hard under the multipoint model even for d = 2 dimensions. We also present hardness results for approximating the probability of the most likely hull. While we focus on the most likely hull for concreteness, our results hold for other natural definitions of a probabilistic hull.
summary: With respect to the convex hull of stochastic points, in the same model that we consider (called unipoint model @cite_0 ), @cite_17 investigated the most likely convex hull of stochastic points, which is the convex hull that appears with the most probability. They proved that such a convex hull can be computed in @math time in the plane, and its computation is NP-hard in higher dimensions.