TY - JOUR

T1 - Separability of imprecise points

AU - Sheikhi, F.

AU - Mohades , A.

AU - de Berg, M.T.

AU - Mehrabi Davoodabadi, A.

PY - 2017/2

Y1 - 2017/2

N2 - 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).

AB - 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).

KW - Imprecise points

KW - Separator

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

U2 - 10.1016/j.comgeo.2016.10.001

DO - 10.1016/j.comgeo.2016.10.001

M3 - Article

VL - 61

SP - 24

EP - 37

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

ER -