Computing the Coarseness of a Bicolored Point Set on the Plane over Guillotine Partitions - Fernandez-Goycoolea, J (IEEE Computer Society, 2023)
The concept of coarseness measures how well blended the elements of a finite bicolored set of n points are. It is defined as the maximum bichromatic discrepancy over all partitions of the set with non-overlapping convex hulls. It is conjectured that this general computation is NP-Hard; hence several simplified lower bounds have been presented in the literature. In this work, we introduce a novel idea of this kind, considering only partitions derived from straight binary divisions of the plane. We call this the guillotine coarseness of the bicolored point set. The basic properties of this concept are studied, and a dynamic programming algorithm of {O}(n{5}) time is presented for calculating it. Finally, experimental simulations are performed to investigate a possible relationship between n and the number k of cuts used to calculate the guillotine coarseness. © 2023 IEEE.