We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of @math points in @math each of which has an existence probability, a SCH refers to the convex hull of a realization of the dataset, i.e., a random sample including each point with its existence probability. We are interested in computing certain expected statistics of a SCH, including diameter, width, and combinatorial complexity. For diameter, we establish the first deterministic 1.633-approximation algorithm with a time complexity polynomial in both @math and @math . For width, two approximation algorithms are provided: a deterministic @math -approximation running in @math time, and a fully polynomial-time randomized approximation scheme (FPRAS). For combinatorial complexity, we propose an exact @math -time algorithm. Our solutions exploit many geometric insights in Euclidean space, some of which might be of independent interest.
@cite_1: We study computing with indecisive point sets. Such points have spatial uncertainty where the true location is one of a finite number of possible locations. This data arises from probing distributions a few times or when the location is one of a few locations from a known database. In particular, we study computing distributions of geometric functions such as the radius of the smallest enclosing ball and the diameter. Surprisingly, we can compute the distribution of the radius of the smallest enclosing ball exactly in polynomial time, but computing the same distribution for the diameter is #P-hard. We generalize our polynomial-time algorithm to all LP-type problems. We also utilize our indecisive framework to deterministically and approximately compute on a more general class of uncertain data where the location of each point is given by a probability distribution.
@cite_3: 
@cite_17: We consider the stochastic geometry model where the location of each node is a random point in a given metric space, or the existence of each node is uncertain. We study the problems of computing the expected lengths of several combinatorial or geometric optimization problems over stochastic points, including closest pair, minimum spanning tree, (k )-clustering, minimum perfect matching, and minimum cycle cover. We also consider the problem of estimating the probability that the length of closest pair, or the diameter, is at most, or at least, a given threshold. Most of the above problems are known to be ( # P )-hard. We obtain FPRAS (Fully Polynomial Randomized Approximation Scheme) for most of them in both the existential and locational uncertainty models. Our result for stochastic minimum spanning trees in the locational uncertain model improves upon the previously known constant factor approximation algorithm. Our results for other problems are the first known to the best of our knowledge.
Specifically, the expected diameter of a SCH was investigated in some recent works. Huang and Li @cite_17 provided an FPRAS for computing the expected farthest-pair distance of a stochastic dataset in a metric space. This directly implies an FPRAS for computing the expected diameter of a SCH, since in Euclidean space the farthest-pair distance of a set of points is just the diameter of their convex hull. However, an FPRAS can only obtain the desired approximation with high probability, and there seems no way to verify whether an answer obtained by the FPRAS is truly a good approximation. @cite_3 gave a deterministic @math -approximation algorithm in @math , which is based on (exactly) computing the expected diameter of the stochastic smallest enclosing ball. Although @cite_3 only considered the case in @math , the algorithm can be naturally extended to compute a @math -approximation of the expected diameter of a SCH in @math . Nevertheless, the runtime of this algorithm grows exponentially as @math increases, since computing the expected diameter of the stochastic smallest enclosing ball requires @math time @cite_1 . The width and combinatorial complexity of a SCH have not yet been investigated previously, to our best knowledge.