2009/05/20 by David Orden, Orden, David, Pedro Ramos +3
Computer Science · Engineering · Mathematics · #52A37 #52C30 #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Mathematics and Applications #math.CO #msc:52A37 #msc:52C30
paper · pdf · doi:10.48550/arxiv.0905.3380
openalex publication_date 2009/05/20 · arxiv created 2009/05/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let B and R be point sets (of \em blue and \em red points, respectively) in the plane, such that P:=B∪ R is in general position, and |P| is even. A line ℓ is \em balanced if it spans one blue and one red point, and on each open halfplane of ℓ, the number of blue points minus the number of red points is the same. We prove that P has at least min \|B|,|R|\ balanced lines. This refines a result by Pach and Pinchasi, who proved this for the case |B|=|R|.