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.