  In this paper, we study the linear separability problem for stochastic
geometric objects under the well-known unipoint/multipoint uncertainty models.
Let $S=S_R \cup S_B$ be a given set of stochastic bichromatic points, and
define $n = \min\{|S_R|, |S_B|\}$ and $N = \max\{|S_R|, |S_B|\}$. We show that
the separable-probability (SP) of $S$ can be computed in $O(nN^{d-1})$ time for
$d \geq 3$ and $O(\min\{nN \log N, N^2\})$ time for $d=2$, while the expected
separation-margin (ESM) of $S$ can be computed in $O(nN^{d})$ time for $d \geq
2$. In addition, we give an $\Omega(nN^{d-1})$ witness-based lower bound for
computing SP, which implies the optimality of our algorithm among all those in
this category. Also, a hardness result for computing ESM is given to show the
difficulty of further improving our algorithm. As an extension, we generalize
the same problems from points to general geometric objects, i.e., polytopes
and/or balls, and extend our algorithms to solve the generalized SP and ESM
problems in $O(nN^{d})$ and $O(nN^{d+1})$ time, respectively. Finally, we
present some applications of our algorithms to stochastic convex-hull related
problems.

Computational Geometry