Robust Bichromatic Classification Using Two Lines
| Title: | Robust Bichromatic Classification Using Two Lines |
|---|---|
| Authors: | Glazenburg, Erwin; van der Horst, Thijs; Peters, Tom; Speckmann, Bettina; Staals, Frank; Sub Geometric Computing; Geometric Computing; Mestre, Julián; Wirth, Anthony |
| Publication Year: | 2024 |
| Subject Terms: | Bichromatic; Classification; Duality; Geometric Algorithms; Separating Line; Software |
| Description: | 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. |
| Document Type: | book part |
| File Description: | application/pdf |
| Language: | English |
| ISSN: | 1868-8969 |
| Relation: | https://dspace.library.uu.nl/handle/1874/482536 |
| Availability: | https://dspace.library.uu.nl/handle/1874/482536 |
| Rights: | info:eu-repo/semantics/OpenAccess |
| Accession Number: | edsbas.67B5DB35 |
| Database: | BASE |