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 ${\mathbb{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 the first 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.

References in corpus (3)

• On the Separability of Stochastic Geometric Objects, with Applications
• Stochastic closest-pair problem and most-likely nearest-neighbor search in tree spaces
• On Dominance-Free Samples of a (Colored) Stochastic Dataset