Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2401.02897 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914963029753856 |
|---|---|
| author | Glazenburg, Erwin van der Horst, Thijs Peters, Tom Speckmann, Bettina Staals, Frank |
| author_facet | Glazenburg, Erwin van der Horst, Thijs Peters, Tom Speckmann, Bettina Staals, Frank |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_02897 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Robust Bichromatic Classification using Two Lines Glazenburg, Erwin van der Horst, Thijs Peters, Tom Speckmann, Bettina Staals, Frank Computational Geometry 68Q25 F.2.2 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. |
| title | Robust Bichromatic Classification using Two Lines |
| topic | Computational Geometry 68Q25 F.2.2 |
| url | https://arxiv.org/abs/2401.02897 |