Separability of imprecise points

详细信息    查看全文

• 作者：Farnaz Sheikhi^a ; Ali Mohades^a ; ¹ ; ^{mohades@aut.ac.ir} ; Mark de Berg^b ; ¹ ; Ali D. Mehrabi^b
• 关键词：Imprecise points ; Separator
• 刊名：Computational Geometry
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：61
• 期：Complete
• 页码：24-37
• 全文大小：585 K
• 卷排序：61

文摘

An imprecise point p   in the plane is a point represented by an imprecision region IpIp indicating the set of possible locations of the point p. We study separability problems for a set R of red imprecise points and a set B   of blue imprecise points, where the imprecision regions are axis-parallel rectangles and each point p∈R∪Bp∈R∪B is drawn uniformly at random from IpIp. Our results include algorithms for finding certain separators (which separate R from B with probability 1), possible separators (which separate R from B with non-zero probability), most likely separators (which separate R from B with maximum probability), and maximal separators (which maximize the expected number of correctly classified points).