### Hyperplane separability and convexity of probabilistic point sets

#### Abstract

We also show that the $d$-dimensional separability problem is equivalent to a $(d+1)$-dimensional convex hull *membership* problem, which asks for the probability that a query point lies inside the convex hull of $n$ probabilistic points. Using this reduction, we improve the current best bound for the convex hull membership problem by a factor of $n$. In addition, our algorithms can handle input degeneracies

in which more than $k+1$ points may lie on a $k$-dimensional subspace, thus resolving an open problem in Agarwal et al 2013. Finally, we prove lower bounds for the separability problem via a reduction from the $k$-SUM problem, which show in particular that our $O(n^2)$ algorithms for $2$-dimensional separability and $3$-dimensional convex hull membership are nearly optimal.

#### Full Text:

PDFDOI: http://dx.doi.org/10.20382/jocg.v8i2a3

ISSN: 1920-180X