New results on the coarseness of bicolored point sets (Q522958)

Consider a set \(S\) of points in the projective real plane in general position, i.e. no three of them are collinear. A \(2\)-coloring of \(S\) is an assignment of one of two colors to each point of \(S\). One of the classical problem regards the decision of whether the colour distribution is well-separated or not, i.e. if there exists some partition of the plane into convex sets so that every element in the partition can be seen as being mostly one of the two colors, or if we have an uniform distribution in which the colors are well-blended. These kind of problems are also interesting for their applications in machine learning, data mining and computer graphics. \textit{S. Bereg} et al. [Comput. Geom. 46, No. 1, 65--77 (2013; Zbl 1251.05026)] introduced the concept of coarseness, which represents a measure of how well blended a given \(2\)-coloring of \(S\) is. In this paper, the authors deal with the following two problems: 1) Given a \(2\)-coloring of \(S\), can its coarseness be approximated to a constant factor in polynomial time? 2) What is the minimum coarseness over all \(2\)-colorings of \(S\)? Regarding the first problem, the authors prove the existence of a polynomial-time algorithm that for a given \(2\)-coloring of \(S\), approximates its coarseness to a constant ratio. Whereas, regarding the second problem, they prove that every set of \(n\) points can be \(2\)-colored such that its coarseness is at most \(O(n^{1/4}\sqrt{\log n})\), which results to be almost tight.