Robust Bichromatic Classification Using Two Lines

Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, Frank Staals

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Titel35th International Symposium on Algorithms and Computation (ISAAC 2024)
Redacteuren Julián Mestre, Anthony Wirth
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pagina's33:1-33:14
Aantal pagina's14
ISBN van elektronische versie978-3-95977-354-6
DOI's
StatusGepubliceerd - 4 dec. 2024
Evenement35th International Symposium on Algorithms and Computation, ISAAC 2024 - Sydney, Australië
Duur: 8 dec. 202411 dec. 2024

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
Volume322
ISSN van elektronische versie1868-8969

Congres

Congres35th International Symposium on Algorithms and Computation, ISAAC 2024
Verkorte titelISAAC 2024
Land/RegioAustralië
StadSydney
Periode8/12/2411/12/24

Vingerafdruk

Duik in de onderzoeksthema's van 'Robust Bichromatic Classification Using Two Lines'. Samen vormen ze een unieke vingerafdruk.

Citeer dit