TY - GEN

T1 - On the separability of stochastic geometric objects, with applications

AU - Xue, Jie

AU - Li, Yuan

AU - Janardan, Ravi

PY - 2016/6/1

Y1 - 2016/6/1

N2 - In this paper, we study the linear separability problem for stochastic geometric objects under the well-known unipoint/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{nN log N, N 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/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{nN log N, N 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=84976907246&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976907246&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2016.62

DO - 10.4230/LIPIcs.SoCG.2016.62

M3 - Conference contribution

AN - SCOPUS:84976907246

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 62.1-62.16

BT - 32nd International Symposium on Computational Geometry, SoCG 2016

A2 - Fekete, Sandor

A2 - Lubiw, Anna

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 32nd International Symposium on Computational Geometry, SoCG 2016

Y2 - 14 June 2016 through 17 June 2016

ER -