We present an algorithm for the 2-clustering problem with cluster size constraints in the plane assuming l1-norm, that works in O(n3logn) time and O(n) space. Such a procedure also solves a full version of the problem, computing the optimal solutions for all possible constraints on cluster sizes. The algorithm is based on a separation result concerning the clusters of any optimal solution of the problem and on an extended version of red-black trees to maintain a bipartition of a set of points in the plane.
Size-constrained 2-clustering in the plane with Manhattan distance / A. Bertoni, M. Goldwurm, J. Lin, L. Pini - In: ICTCS 2014 : Italian Conference on Theoretical Computer Science : proceedings of the 15th Italian Conference on Theoretical Computer Science Perugia, Italy, September 17-19, 2014 / [a cura di] S. Bistarelli, A. Formisano. - [s.l] : CEUR-WS, 2014. - pp. 33-44 (( Intervento presentato al 15. convegno ICTCS 2014 tenutosi a Perugia nel 2014.
Size-constrained 2-clustering in the plane with Manhattan distance
A. BertoniPrimo
;M. GoldwurmSecondo
;J. Lin
;
2014
Abstract
We present an algorithm for the 2-clustering problem with cluster size constraints in the plane assuming l1-norm, that works in O(n3logn) time and O(n) space. Such a procedure also solves a full version of the problem, computing the optimal solutions for all possible constraints on cluster sizes. The algorithm is based on a separation result concerning the clusters of any optimal solution of the problem and on an extended version of red-black trees to maintain a bipartition of a set of points in the plane.File | Dimensione | Formato | |
---|---|---|---|
long2.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
554.73 kB
Formato
Adobe PDF
|
554.73 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.