DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2024.33

Robust Bichromatic Classification Using Two Lines

Authors: Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, and Frank Staals

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract

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 𝒲_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(nlog n) up to around O(n³), depending on the type of region 𝒲_B and whether we wish to minimize only red outliers, only blue outliers, or both.

Cite as

Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, and Frank Staals. Robust Bichromatic Classification Using Two Lines. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{glazenburg_et_al:LIPIcs.ISAAC.2024.33,
  author =	{Glazenburg, Erwin and van der Horst, Thijs and Peters, Tom and Speckmann, Bettina and Staals, Frank},
  title =	{{Robust Bichromatic Classification Using Two Lines}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.33},
  URN =		{urn:nbn:de:0030-drops-221605},
  doi =		{10.4230/LIPIcs.ISAAC.2024.33},
  annote =	{Keywords: Geometric Algorithms, Separating Line, Classification, Bichromatic, Duality}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2024.34

Robust Classification of Dynamic Bichromatic Point Sets in R²

Authors: Erwin Glazenburg, Marc van Kreveld, and Frank Staals

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract

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.

Cite as

Erwin Glazenburg, Marc van Kreveld, and Frank Staals. Robust Classification of Dynamic Bichromatic Point Sets in R². In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{glazenburg_et_al:LIPIcs.ISAAC.2024.34,
  author =	{Glazenburg, Erwin and van Kreveld, Marc and Staals, Frank},
  title =	{{Robust Classification of Dynamic Bichromatic Point Sets in R²}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.34},
  URN =		{urn:nbn:de:0030-drops-221615},
  doi =		{10.4230/LIPIcs.ISAAC.2024.34},
  annote =	{Keywords: classification, duality, data structures, dynamic, linear programming}
}

Search Results

Documents authored by Glazenburg, Erwin

Robust Bichromatic Classification Using Two Lines

Abstract

Cite as

Robust Classification of Dynamic Bichromatic Point Sets in R²

Abstract

Cite as

Thanks for your feedback!

Could not send message