Robust Classification of Dynamic Bichromatic Point Sets in R²

Let R ∪ B be a set of n points in R², and let k ∈ 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 + ε)-approximation algorithm runs in O(ε⁻¹/²((n + k²) log n)) time. Based on our (1 + ε)-approximation algorithm we then also obtain a semi-online data structure to maintain such a separator efficiently.