Computing the coarseness of a bicolored point set on the plane over guillotine partitions
- 1
- 2Universidad Tecnológica Metropolitana
- 3Universitat Politècnica de Catalunya
Journal
proceedings - international conference of the chilean computer science society, sccc
ISSN
1522-4902
Open Access
closed
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.