Xue, Jie ;
Li, Yuan ;
Janardan, Ravi
On the Separability of Stochastic Geometric Objects, with Applications
Abstract
In this paper, we study the linear separability problem for stochastic geometric objects under the wellknown unipoint/multipoint uncertainty models. Let S=S_R U S_B be a given set of stochastic bichromatic points, and define n = min{S_R, S_B} and N = max{S_R, S_B}. We show that the separableprobability (SP) of S can be computed in O(nN^{d1}) time for d >= 3 and O(min{nN log N, N^2}) time for d=2, while the expected separationmargin (ESM) of S can be computed in O(nN^d) time for d >= 2. In addition, we give an Omega(nN^{d1}) witnessbased 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(nN^d) and O(nN^{d+1}) time, respectively. Finally, we present some applications of our algorithms to stochastic convexhull related problems.
BibTeX  Entry
@InProceedings{xue_et_al:LIPIcs:2016:5954,
author = {Jie Xue and Yuan Li and Ravi Janardan},
title = {{On the Separability of Stochastic Geometric Objects, with Applications}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {62:162:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5954},
URN = {urn:nbn:de:0030drops59544},
doi = {10.4230/LIPIcs.SoCG.2016.62},
annote = {Keywords: Stochastic objects, linear separability, separableprobability, expected separationmargin, convex hull}
}
2016
Keywords: 

Stochastic objects, linear separability, separableprobability, expected separationmargin, convex hull 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

2016 