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 WB 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) up to around O(n3), depending on the type of region WB and whether we wish to minimize only red outliers, only blue outliers, or both.