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. Bertoni
Primo
;
M. Goldwurm
Secondo
;
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.
Algorithms and data structures; Cluster size constraints; Clustering; Manhattan distance
Settore INF/01 - Informatica
Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni
2014
Dipartimento di Matematica e Informatica
EATCS
Provincia di Perugia
Regione Umbria
Universita di Perugia
Book Part (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/249928
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact