Robust Bichromatic Classification using Two Lines
| Autor: | Glazenburg, Erwin, van der Horst, Thijs, Peters, Tom, Speckmann, Bettina, Staals, Frank |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $\mathcal{W}_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(n\log n)$ and around $O(n^3)$, depending on the type of region $\mathcal{W}_B$ and whether we wish to minimize only red outliers, only blue outliers, or both. Comment: 26 pages, 17 figures. Full version of article to be presented at ISAAC24 |
| Databáze: | arXiv |
| Externí odkaz: |
|