Robust Bichromatic Classification Using Two Lines

Erwin Glazenburg; Thijs van der Horst; Tom Peters; Bettina Speckmann; Frank Staals

doi:10.4230/LIPIcs.ISAAC.2024.33

Robust Bichromatic Classification Using Two Lines

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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

Original language	English
Title of host publication	35th International Symposium on Algorithms and Computation (ISAAC 2024)
Editors	Julián Mestre, Anthony Wirth
Publisher	Dagstuhl Publishing
Pages	33:1-33:14
Number of pages	14
ISBN (Electronic)	978-3-95977-354-6
ISBN (Print)	978-3-95977-354-6
DOIs	https://doi.org/10.4230/LIPIcs.ISAAC.2024.33
Publication status	Published - 4 Dec 2024

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	322
ISSN (Print)	1868-8969

Bibliographical note

Publisher Copyright:
© Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, and Frank Staals.

Keywords

Bichromatic
Classification
Duality
Geometric Algorithms
Separating Line

Access to Document

10.4230/LIPIcs.ISAAC.2024.33Licence: CC BY

LIPIcs.ISAAC.2024.33Final published version, 1.01 MBLicence: CC BY

Cite this

Glazenburg, E., van der Horst, T., Peters, T., Speckmann, B., & Staals, F. (2024). Robust Bichromatic Classification Using Two Lines. In J. Mestre, & A. Wirth (Eds.), 35th International Symposium on Algorithms and Computation (ISAAC 2024) (pp. 33:1-33:14). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 322). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2024.33

@inproceedings{d7eeb41eed4548abbd4d48512f4c0fb6,

title = "Robust Bichromatic Classification Using Two Lines",

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 WB 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) up to around O(n3), depending on the type of region WB and whether we wish to minimize only red outliers, only blue outliers, or both.",

keywords = "Bichromatic, Classification, Duality, Geometric Algorithms, Separating Line",

author = "Erwin Glazenburg and {van der Horst}, Thijs and Tom Peters and Bettina Speckmann and Frank Staals",

note = "Publisher Copyright: {\textcopyright} Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, and Frank Staals.",

year = "2024",

month = dec,

day = "4",

doi = "10.4230/LIPIcs.ISAAC.2024.33",

language = "English",

isbn = "978-3-95977-354-6",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Dagstuhl Publishing",

pages = "33:1--33:14",

editor = "Juli{\'a}n Mestre and Anthony Wirth",

booktitle = "35th International Symposium on Algorithms and Computation (ISAAC 2024)",

}

Glazenburg, E , van der Horst, T, Peters, T, Speckmann, B & Staals, F 2024, Robust Bichromatic Classification Using Two Lines. in J Mestre & A Wirth (eds), 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics, LIPIcs, vol. 322, Dagstuhl Publishing, pp. 33:1-33:14. https://doi.org/10.4230/LIPIcs.ISAAC.2024.33

Robust Bichromatic Classification Using Two Lines. / Glazenburg, Erwin ; van der Horst, Thijs; Peters, Tom et al.
35th International Symposium on Algorithms and Computation (ISAAC 2024). ed. / Julián Mestre; Anthony Wirth. Dagstuhl Publishing, 2024. p. 33:1-33:14 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 322).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Robust Bichromatic Classification Using Two Lines

AU - Glazenburg, Erwin

AU - van der Horst, Thijs

AU - Peters, Tom

AU - Speckmann, Bettina

AU - Staals, Frank

PY - 2024/12/4

Y1 - 2024/12/4

N2 - 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 WB 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) up to around O(n3), depending on the type of region WB and whether we wish to minimize only red outliers, only blue outliers, or both.

AB - 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 WB 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) up to around O(n3), depending on the type of region WB and whether we wish to minimize only red outliers, only blue outliers, or both.

KW - Bichromatic

KW - Classification

KW - Duality

KW - Geometric Algorithms

KW - Separating Line

UR - http://www.scopus.com/inward/record.url?scp=85213065922&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2024.33

DO - 10.4230/LIPIcs.ISAAC.2024.33

M3 - Conference contribution

SN - 978-3-95977-354-6

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 33:1-33:14

BT - 35th International Symposium on Algorithms and Computation (ISAAC 2024)

A2 - Mestre, Julián

A2 - Wirth, Anthony

PB - Dagstuhl Publishing

ER -

Robust Bichromatic Classification Using Two Lines

Abstract

Publication series

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this