View article

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 ³) time for n points in d = 2 dimensions, but it is NP–hard for d ≥ 3 dimensions. On the …