In this paper, we study the linear separability problem for stochastic geometric objects under the well-known unipoint multipoint uncertainty models. Let @math be a given set of stochastic bichromatic points, and define @math and @math . We show that the separable-probability (SP) of @math can be computed in @math time for @math and @math time for @math , while the expected separation-margin (ESM) of @math can be computed in @math time for @math . In addition, we give an @math 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 @math and @math time, respectively. Finally, we present some applications of our algorithms to stochastic convex-hull related problems.
@cite_3: An imprecise point is a point p with an associated imprecision region ( I _p ) indicating the set of possible locations of the point p. We study separability problems for a set R of red imprecise points and a set B of blue imprecise points in ( R ^2 ), where the imprecision regions are axis-aligned rectangles and each point p ∈ R ∪ B is drawn uniformly at random from ( I _p ). Our results include algorithms for finding certain separators (separating R from B with probability 1), possible separators (separating R from B with non-zero probability), most likely separators (separating R from B with maximal probability), and maximal separators (maximizing the expected number of correctly classified points).
Recently, in @cite_3 , de studied the separability problem given a set of bichromatic imprecise points in @math in a setting that each point is drawn from an imprecision region.