Balanced lines in two-coloured point sets

MaRDI QIDQ6214017zbMATH OpenFDO

Authors David Orden, Pedro Ramos, Gelasio Salazar

Publication date 20 May 2009

Mathematics Subject Classification ID

Other problems of combinatorial convexity (52A37) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Abstract: Let $B$ and $R$ be point sets (of {em blue} and {em red} points, respectively) in the plane, such that $P:=BcupR$ is in general position, and $|P|$ is even. A line $ell$ is {em balanced} if it spans one blue and one red point, and on each open halfplane of $ell$, 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|$.

This page was built for publication: Balanced lines in two-coloured point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6214017)