2026-09-05T07:04:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26065 2026-06-23T13:18:50Z ddc:004 open_access

Bichromatic Classifications of Points Using Strips Lee, Jaegun Chung, Chaeyoon Ahn, Hee-Kap Bichromatic Classification Separation Strip Duality Given a set of n points in the plane, each colored either blue or red, we study the problem of finding a strip that separates the blue points from the red points. Specifically, we consider the following two variants: (1) locating a strip that contains no red points while maximizing the number of blue points within the strip, and (2) locating a strip that contains all blue points while minimizing the number of red points within the strip. For variant (1), we present an O(n²)-time algorithm, improving upon the previously best O(n²log n)-time result. We also show that this running time is optimal under the standard 3SUM conjecture. We also give an output-sensitive algorithm with running time O(k_{opt} n log n) that returns a strip, where k_{opt} is the number of blue points not contained within the strip in an optimal solution. We extend our results to the case of up to t parallel strips, obtaining an O(n²log n)-time algorithm. For variant (2), an optimal Θ(nlog n)-time algorithm is known for t = 1. We show 3SUM-hardness for t = 2 and give an O(n²)-time algorithm. For any t ≥ 3, we present an O(n²log n)-time algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jaegun Lee and Chaeyoon Chung and Hee-Kap Ahn 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.29 urn:nbn:de:0030-drops-260659 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.29 eng https://creativecommons.org/licenses/by/4.0/legalcode