Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950778 | Information Processing Letters | 2017 | 7 Pages |
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(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).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
J.M. DÃaz-Báñez, R. Fabila-Monroy, P. Pérez-Lantero, I. Ventura,