2026-07-23T20:44:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5930 2024-03-06T10:37:18Z ddc:004 open_access

Hyperplane Separability and Convexity of Probabilistic Point Sets Fink, Martin Hershberger, John Kumar, Nirman Suri, Subhash probabilistic separability uncertain data 3-SUM hardness topological sweep hyperplane separation multi-dimensional data We describe an O(n^d) time algorithm for computing the exact probability that two d-dimensional probabilistic point sets are linearly separable, for any fixed d >= 2. A probabilistic point in d-space is the usual point, but with an associated (independent) probability of existence. We also show that the d-dimensional separability problem is equivalent to a (d+1)-dimensional convex hull membership problem, which asks for the probability that a query point lies inside the convex hull of n probabilistic points. Using this reduction, we improve the current best bound for the convex hull membership by a factor of n [Agarwal et al., ESA, 2014]. In addition, our algorithms can handle "input degeneracies" in which more than k+1 points may lie on a k-dimensional subspace, thus resolving an open problem in [Agarwal et al., ESA, 2014]. Finally, we prove lower bounds for the separability problem via a reduction from the k-SUM problem, which shows in particular that our O(n^2) algorithms for 2-dimensional separability and 3-dimensional convex hull membership are nearly optimal. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Fink and John Hershberger and Nirman Kumar and Subhash Suri 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.38 urn:nbn:de:0030-drops-59305 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.38 eng https://creativecommons.org/licenses/by/3.0/legalcode