| Title: |
Robust Classification of Dynamic Bichromatic Point Sets in R2 |
| Authors: |
Glazenburg, Erwin; van Kreveld, Marc; Staals, Frank; Sub Geometric Computing; Dep Informatica; Mestre, Julian; Wirth, Anthony |
| Publication Year: |
2024 |
| Subject Terms: |
classification; data structures; duality; dynamic; linear programming; Software |
| Description: |
Let R ∪ B be a set of n points in R2, and let k ∈ 1.n. Our goal is to compute a line that “best” separates the “red” points R from the “blue” points B with at most k outliers. We present an efficient semi-online dynamic data structure that can maintain whether such a separator exists (“semi-online” meaning that when a point is inserted, we know when it will be deleted). Furthermore, we present efficient exact and approximation algorithms that compute a linear separator that is guaranteed to misclassify at most k, points and minimizes the distance to the farthest outlier. Our exact algorithm runs in O(nk + n log n) time, and our (1 + ε)-approximation algorithm runs in O(ε−1/2((n + k2) log n)) time. Based on our (1 + ε)-approximation algorithm we then also obtain a semi-online data structure to maintain such a separator efficiently. |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
1868-8969 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/482606 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/482606 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.4EDE36AF |
| Database: |
BASE |