Robust Classification of Dynamic Bichromatic point Sets in R2

Abstract

Let $R\cup B$ be a set of $n$ points in ${\mathbb{R}}^2$, and let $k\in \mathrm{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+\epsilon )$-approximation algorithm runs in $O({\epsilon }^{-1/2}((n+k^2)\log n))$ time. Based on our $(1+\epsilon )$-approximation algorithm we then also obtain a semi-online data structure to maintain such a separator efficiently.

43 pages, 32 figures