Robust Bichromatic Classification using Two Lines

Abstract

Given two sets $R$ and $B$ of $n$ points in the plane, we present efficient algorithms to find a two-line linear classifier that best separates the "red" points in $R$ from the "blue" points in $B$ and is robust to outliers. More precisely, we find a region ${\mathcal{W}}_B$ bounded by two lines, so either a halfplane, strip, wedge, or double wedge, containing (most of) the blue points $B$, and few red points. Our running times vary between optimal $O(n\log n)$ and around $O(n^3)$, depending on the type of region ${\mathcal{W}}_B$ and whether we wish to minimize only red outliers, only blue outliers, or both.

26 pages, 17 figures. Full version of article to be presented at ISAAC24