Separability of imprecise points

M.T. Berg, de, A.D. Mehrabi, F. Sheikhi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)


An imprecise point is a point p with an associated imprecision region Ip 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 in R2 , where the imprecision regions are axis-aligned rectangles and each point p¿¿¿R¿¿¿B is drawn uniformly at random from Ip . Our results include algorithms for finding certain separators (separating R from B with probability 1), possible separators (separating R from B with non-zero probability), most likely separators (separating R from B with maximal probability), and maximal separators (maximizing the expected number of correctly classified points).
Original languageEnglish
Title of host publicationAlgorithm Theory – SWAT 2014 (14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings)
EditorsR. Ravi, I.L. Gørtz
Place of PublicationBerlin
ISBN (Print)978-3-319-08403-9
Publication statusPublished - 2014
Event14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014) - Copenghagen, Denmark
Duration: 2 Jul 20144 Jul 2014
Conference number: 14

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014)
Abbreviated titleSWAT 2014


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

Cite this