2026-07-26T21:51:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22161 2024-12-04T06:53:44Z ddc:004 open_access

Robust Classification of Dynamic Bichromatic Point Sets in R² Glazenburg, Erwin van Kreveld, Marc Staals, Frank classification duality data structures dynamic linear programming Let R ∪ B be a set of n points in R², 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 + k²) log n)) time. Based on our (1+ε)-approximation algorithm we then also obtain a semi-online data structure to maintain such a separator efficiently. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erwin Glazenburg and Marc van Kreveld and Frank Staals 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.34 urn:nbn:de:0030-drops-221615 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.34 eng https://creativecommons.org/licenses/by/4.0/legalcode