首页    期刊浏览 2024年11月07日 星期四
登录注册

文章基本信息

  • 标题:Hyperplane Separability and Convexity of Probabilistic Point Sets
  • 本地全文:下载
  • 作者:Martin Fink ; John Hershberger ; Nirman Kumar
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2016
  • 卷号:51
  • 页码:38:1-38:16
  • DOI:10.4230/LIPIcs.SoCG.2016.38
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:probabilistic separability; uncertain data; 3-SUM hardness; topological sweep; hyperplane separation; multi-dimensional data
国家哲学社会科学文献中心版权所有