Computing the coarseness measure of a bicolored point set over guillotine partitions
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 com...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-11-01
|
| Series: | Results in Applied Mathematics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2590037424000736 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846119432846311424 |
|---|---|
| author | José Fernández Goycoolea Luis H. Herrera Pablo Pérez-Lantero Carlos Seara |
| author_facet | José Fernández Goycoolea Luis H. Herrera Pablo Pérez-Lantero Carlos Seara |
| author_sort | José Fernández Goycoolea |
| collection | DOAJ |
| description | 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(n2log2n) 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. |
| format | Article |
| id | doaj-art-6b7e31a97e5c4e7ebf9feece4ceb41d7 |
| institution | Kabale University |
| issn | 2590-0374 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Results in Applied Mathematics |
| spelling | doaj-art-6b7e31a97e5c4e7ebf9feece4ceb41d72024-12-17T05:00:27ZengElsevierResults in Applied Mathematics2590-03742024-11-0124100503Computing the coarseness measure of a bicolored point set over guillotine partitionsJosé Fernández Goycoolea0Luis H. Herrera1Pablo Pérez-Lantero2Carlos Seara3Departamento de Matemática y Física, Universidad de Magallanes, Avenida Bulnes 01855, Punta Arenas, Chile; Departamento de Ingeniería Informática, Universidad de Santiago de Chile, Las Sophoras 173, Santiago de Chile, Región Metropolitana, ChileDepartamento de Informática y Computación, Universidad Tecnológica Metropolitana, José Pedro Alessandri 1242, Ñuñoa, Santiago de Chile 7800002, Región Metropolitana, ChileDepartamento de Matemática y Ciencia de la Computación, Universidad de Santiago de Chile (USACH), Las Sophoras 173, Santiago de Chile, Región Metropolitana, ChileDepartament de Matemàtiques, Universitat Politècnica de Catalunya, Jordi Girona 1, 08034 Barcelona, Spain; Corresponding author.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(n2log2n) 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.http://www.sciencedirect.com/science/article/pii/S2590037424000736Coarseness measureDiscrepancyClusteringGuillotine partitionDynamic programming |
| spellingShingle | José Fernández Goycoolea Luis H. Herrera Pablo Pérez-Lantero Carlos Seara Computing the coarseness measure of a bicolored point set over guillotine partitions Results in Applied Mathematics Coarseness measure Discrepancy Clustering Guillotine partition Dynamic programming |
| title | Computing the coarseness measure of a bicolored point set over guillotine partitions |
| title_full | Computing the coarseness measure of a bicolored point set over guillotine partitions |
| title_fullStr | Computing the coarseness measure of a bicolored point set over guillotine partitions |
| title_full_unstemmed | Computing the coarseness measure of a bicolored point set over guillotine partitions |
| title_short | Computing the coarseness measure of a bicolored point set over guillotine partitions |
| title_sort | computing the coarseness measure of a bicolored point set over guillotine partitions |
| topic | Coarseness measure Discrepancy Clustering Guillotine partition Dynamic programming |
| url | http://www.sciencedirect.com/science/article/pii/S2590037424000736 |
| work_keys_str_mv | AT josefernandezgoycoolea computingthecoarsenessmeasureofabicoloredpointsetoverguillotinepartitions AT luishherrera computingthecoarsenessmeasureofabicoloredpointsetoverguillotinepartitions AT pabloperezlantero computingthecoarsenessmeasureofabicoloredpointsetoverguillotinepartitions AT carlosseara computingthecoarsenessmeasureofabicoloredpointsetoverguillotinepartitions |