Separability of imprecise points (Q2362104)

The authors deal with some separability problems of imprecise points (points of which the location is not known precisely). In separability problems we have two sets of points (red and blue) and the goal is to decide whether the red points can be separated from the blue points by a separator from a given class of geometric objects. Such problems arise in data-analysis problems that involve geometric data, e.g., data obtained by LIDAR or GPS. In the paper the authors extend the region-based imprecision model to include probabilistic aspects, i.e., we assume that each point is drawn from its imprecision region according to some distribution. In the paper the uniform distribution is considered. The study starts with the results regarding the certain separators, i.e., a separator that separates the red points from the blue points with probability \(1\). The authors show that finding such separators in the class of linear and rectangular separators can be done in \(O(n)\) time, where \(n\) is the number of all points. Then, they present how to find possible separators (a separator that separates the red points from the blue points with non-zero probability). The presented algorithms run in \(O(n \log n)\) for a possible linear separator and \(O(n)\) for the possible rectangular separator. Moreover, they show how to compute all possible linear separators in \(O(n \log n)\) time and all possible rectangular separators in \(O(n^2 \log n)\) time. The next considered problem is the problem of finding of the most likely separators, i.e., separators that separate the red points from the blue points with maximum probability. Because this type of separators is a lot harder to find the authors study only the one-dimensional case. They show that we can find an elementary interval that contains the most likely separator in \(O(n \log n)\) time. Next, the attention of the authors is focused on the weak separability, i.e., separability in which the goal is to maximize the number of correctly classified points. They present exact algorithms for linear, rectangular separators and rectangular separators when the imprecision regions are horizontal segments that run in \(O(n^2)\), \(O(n^3 \log n)\) and \(O(n^2 \sqrt{n})\) time, respectively. Moreover, they present the \((1-\varepsilon)\)-approximation algorithms for weak separability for linear and rectangular separators that run in \(O(n \cdot poly(1/\varepsilon))\) time, where \(poly(1/\varepsilon)\) denotes a polynomial in \(1/\varepsilon\).