Separability of imprecise points

F. Sheikhi, A. Mohades (Corresponding author), M.T. de Berg, A. Mehrabi Davoodabadi

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
1 Downloads (Pure)


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).
Original languageEnglish
Pages (from-to)24–37
Number of pages14
JournalComputational Geometry
Publication statusPublished - Feb 2017


  • Imprecise points
  • Separator

Fingerprint Dive into the research topics of 'Separability of imprecise points'. Together they form a unique fingerprint.

Cite this