Robust Classification of Dynamic Bichromatic point Sets in R2
<|reference_start|>Robust Classification of Dynamic Bichromatic point Sets in R2: Let $R \cup B$ be a set of $n$ points in $\mathbb{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. 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+\varepsilon)$-approximation algorithm runs in $O(\varepsilon^{-1/2}((n + k^2) \log n))$ time. Based on our $(1+\varepsilon)$-approximation algorithm we then also obtain a semi-online data structure to maintain such a separator efficiently.<|reference_end|>
@article{glazenburg2024robust,
    title={Robust Classification of Dynamic Bichromatic point Sets in R2},
    author={Erwin Glazenburg, Frank Staals, Marc van Kreveld},
    journal={arXiv preprint arXiv:2406.19161},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.19161},
    primaryClass={cs.CG}
}