TY - JOUR
T1 - On the separability of stochastic geometric objects, with applications
AU - Xue, Jie
AU - Li, Yuan
AU - Janardan, Ravi
N1 - Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2018/10
Y1 - 2018/10
N2 - In this paper, we study the linear separability problem for stochastic geometric objects under the well-known unipoint and multipoint uncertainty models. Let S=SR∪SB be a given set of stochastic bichromatic points, and define n=min{|SR|,|SB|} and N=max{|SR|,|SB|}. We show that the separable-probability (SP) of S can be computed in O(nNd−1) time for d≥3 and O(min{nNlogN,N2}) time for d=2, while the expected separation-margin (ESM) of S can be computed in O(nNd) time for d≥2. In addition, we give an Ω(nNd−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(nNd) and O(nNd+1) time, respectively. Finally, we present some applications of our algorithms to stochastic convex hull-related problems.
AB - In this paper, we study the linear separability problem for stochastic geometric objects under the well-known unipoint and multipoint uncertainty models. Let S=SR∪SB be a given set of stochastic bichromatic points, and define n=min{|SR|,|SB|} and N=max{|SR|,|SB|}. We show that the separable-probability (SP) of S can be computed in O(nNd−1) time for d≥3 and O(min{nNlogN,N2}) time for d=2, while the expected separation-margin (ESM) of S can be computed in O(nNd) time for d≥2. In addition, we give an Ω(nNd−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(nNd) and O(nNd+1) time, respectively. Finally, we present some applications of our algorithms to stochastic convex hull-related problems.
KW - Convex hull
KW - Expected separation-margin
KW - Linear separability
KW - Separable-probability
KW - Stochastic objects
UR - http://www.scopus.com/inward/record.url?scp=85048834244&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048834244&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2018.06.001
DO - 10.1016/j.comgeo.2018.06.001
M3 - Article
AN - SCOPUS:85048834244
SN - 0925-7721
VL - 74
SP - 1
EP - 20
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
ER -