New results on the coarseness of bicolored point sets

Abstract Let S be a set n points in general position in the plane. A 2-coloring of S is an assignment of one of two colors (red or blue) to each point of S . Recently, a parameter called coarseness was introduced by Bereg et al. (2013) [7] ; it is a measure of how well blended a given 2-coloring of S is. Informally, the coarseness of a 2-coloring is high when S can be split into blocks, each with a large difference in its number of red and blue points. In this paper, we study two questions related to this parameter: Given a 2-coloring of S , can its coarseness be approximated to a constant factor in polynomial time? What is the minimum coarseness over all 2-colorings of S ? For the first problem, we show that there exists a polynomial-time algorithm that for a given 2-coloring of S , approximates its coarseness to a constant ratio. For the second problem, we prove that every set of n points can be 2-colored such that its coarseness is at most O ( n 1 / 4 log ⁡ n ) . We show that this bound is almost tight since there exist sets of n points such that every 2-coloring has coarseness at least Ω ( n 1 / 4 ) .