Robust Bichromatic Classification using Two Lines

Abstract

Given two sets \(R\) and \(B\) of \(n\) points in the plane, we present efficient algorithms to find a two-line linear classifier that best separates the “red” points in \(R\) from the “blue” points in \(B\) and is robust to outliers. More precisely, we find a region \(W_B\) bounded by two lines, so either a halfplane, strip, wedge, or double wedge, containing (most of) the blue points \(B\), and few red points. Our running times vary between optimal \(O(n\log n)\) and around \(O(n^3)\), depending on the type of region \(W_B\) and whether we wish to minimize only red outliers, only blue outliers, or both.

Corresponding Publications

Robust Bichromatic Classification using Two Lines

Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, Frank Staals

Proc. 35th International Symposium on Algorithms and Computation, 2024

To appear
Download Local Copy View Slides Export Citation 
@inproceedings{twolineseparator2024,
  author = {Glazenburg, Erwin and van der Horst, Thijs and Peters, Tom and Speckmann, Bettina and Staals, Frank},
  title = {Robust Bichromatic Classification using Two Lines},
  booktitle = {Proc. 35th International Symposium on Algorithms and Computation},
  year = {2024},
  location = {Sydney, Australia},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  category = {classification},
  note = {To appear},
}

Robust Bichromatic Classification using Two Lines

Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, Frank Staals

Abstr. 40th European Workshop on Computational Geometry (EuroCG), 2024

Download Local Copy View Slides Export Citation 
@article{twolineseparator_eurocg,
  author = {Glazenburg, Erwin and van der Horst, Thijs and Peters, Tom and Speckmann, Bettina and Staals, Frank},
  title = {Robust Bichromatic Classification using Two Lines},
  journal = {Abstr. 40th European Workshop on Computational Geometry (EuroCG)},
  year = {2024},
  location = {Ioannina, Greece},
  numpages = {6},
  category = {classification},
  project = {twolineseparator2024},
}