Computing the coarseness measure of a bicolored point set over guillotine partitions
Herrera, Luis H.
Universidad Tecnologica Metropolitana
Perez-Lantero, Pablo
Univ Santiago De Chile USACH
Seara, Carlos
Universitat Politecnica de Catalunya
Journal
Results in Applied Mathematics
ISSN
2590-0374
Open Access
gold
Volume
24
The coarseness of a set of points in the plane colored red and blue is a measure of how well the points are mixed together. It has appealing theoretical properties, including a connection to the set of points tendency to accept a good clustering partition. Yet, it is computationally expensive to compute exactly. In this paper, the notion of computing the coarseness using a guillotine partition approach is introduced, and efficient algorithms for computing this guillotine coarseness are presented: a top-down approach and a dynamic programming approach, both of them achieving polynomial time and space complexities. Finally, an even faster O ( n 2 log 2 n) polynomial-time algorithm to compute a reduced version of the measurement named two- level guillotine coarseness is presented using geometric data structures for faster computations. These restrictions establish lower bounds for the general guillotine coarseness that allow the development of more efficient algorithms for computing it.