On the expected diameter, width, and complexity of a stochastic convex hull

Abstract We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of n points in R d 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 a deterministic 1.633-approximation algorithm with a time complexity polynomial in both n and d . For width, two approximation algorithms are provided: a deterministic O ( 1 ) -approximation running in O ( n d + 1 log ⁡ n ) time, and a fully polynomial-time randomized approximation scheme (FPRAS). For combinatorial complexity, we propose an exact O ( n d ) -time algorithm. Our solutions exploit many geometric insights in Euclidean space, some of which might be of independent interest.