New Results on the Coarseness of Bicolored Point Sets

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(n1/4log⁡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 Ω(n1/4). © 2017 Elsevier B.V.