TY - GEN
T1 - Robust Bichromatic Classification Using Two Lines
AU - Glazenburg, Erwin
AU - van der Horst, Thijs
AU - Peters, Tom
AU - Speckmann, Bettina
AU - Staals, Frank
PY - 2024/12/4
Y1 - 2024/12/4
N2 - 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.
AB - 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.
KW - Bichromatic
KW - Classification
KW - Duality
KW - Geometric Algorithms
KW - Separating Line
UR - http://www.scopus.com/inward/record.url?scp=85213065922&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2024.33
DO - 10.4230/LIPIcs.ISAAC.2024.33
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics (LIPIcs)
SP - 33:1-33:14
BT - 35th International Symposium on Algorithms and Computation (ISAAC 2024)
A2 - Mestre, Julián
A2 - Wirth, Anthony
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 35th International Symposium on Algorithms and Computation, ISAAC 2024
Y2 - 8 December 2024 through 11 December 2024
ER -