Separability of imprecise points

An imprecise point is a point p with an associated imprecision region Ip 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 R2 , where the imprecision regions are axis-aligned rectangles and each point p¿¿¿R¿¿¿B is drawn uniformly at random from Ip . 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)