Robust Classification of Dynamic Bichromatic Point Sets in \(\R^2\)

Abstract

Let \(R \cup B\) be a set of \(n\) points in \(\R^2\), and let \(k \in 1..n\). Our goal is to compute a line that “best” separates the “red” points \(R\) from the “blue” points \(B\) with at most \(k\) outliers. We present an efficient semi-online dynamic data structure that can maintain whether such a separator exists (‘semi-online’ meaning that when a point is inserted, we know when it will be deleted). Furthermore, we present efficient exact and approximation algorithms that compute a linear separator that is guaranteed to misclassify at most \(k\), points and minimizes the distance to the farthest outlier. Our exact algorithm runs in \(O(nk + n \log n)\) time, and our \((1+\eps)\)-approximation algorithm runs in \(O(\eps^{-1/2}((n + k^2) \log n))\) time. Based on our \((1+\eps)\)-approximation algorithm we then also obtain a semi-online data structure to maintain such a separator efficiently.

Corresponding Publications

Robust Classification of Dynamic Bichromatic Point Sets in \(\R^2\)

Erwin Glazenburg, Marc Kreveld, Frank Staals

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

To appear
Download Local Copy View Slides Export Citation 
@inproceedings{dynamicsvm2024,
  author = {Glazenburg, Erwin and Kreveld, Marc and Staals, Frank},
  title = {Robust Classification of Dynamic Bichromatic Point Sets in $\R^2$},
  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},
}

Classification of bichromatic points with outliers

Erwin Glazenburg, Marc Kreveld, Frank Staals

Abstr. 39th European Workshop on Computational Geometry (EuroCG), 2023

Download Local Copy View Slides Export Citation 
@article{dynamicsvm_eurocg,
  author = {Glazenburg, Erwin and Kreveld, Marc and Staals, Frank},
  title = {Classification of bichromatic points with outliers},
  journal = {Abstr. 39th European Workshop on Computational Geometry (EuroCG)},
  year = {2023},
  location = {Barcelona, Spain},
  numpages = {8},
  category = {algorithms},
  project = {dynamicsvm2024},
}