@inproceedings{789a2f5d094d4270b48b6f164e36cc8a,
title = "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 𝒲\_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(nlog n) up to around O(n³), depending on the type of region 𝒲\_B and whether we wish to minimize only red outliers, only blue outliers, or both.",
keywords = "Bichromatic, Classification, Duality, Geometric Algorithms, Separating Line",
author = "Erwin Glazenburg and \{van der Horst\}, Thijs and Tom Peters and Bettina Speckmann and Frank Staals",
year = "2024",
month = dec,
day = "4",
doi = "10.4230/LIPIcs.ISAAC.2024.33",
language = "English",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "33:1--33:14",
editor = "Mestre, \{ Juli{\'a}n\} and Wirth, \{ Anthony\}",
booktitle = "35th International Symposium on Algorithms and Computation (ISAAC 2024)",
note = "35th International Symposium on Algorithms and Computation, ISAAC 2024, ISAAC 2024 ; Conference date: 08-12-2024 Through 11-12-2024",
}