We study the problem of determining an optimal bipartition {A, B}of a set X of n points in R^2, under the size constraints |A| =k and |B| = n −k, that minimizes the dispersion of points around their centroid in A and B, both in the cases of Euclidean and Manhattan norms. Under the Euclidean norm, we show that the problem can be solved in O(n k^(1/3) log^2 n) time by using known properties on k-sets and convex hulls; moreover, the solutions for all k =1, 2, ..., n/2 can be computed in O(n^2 log n) time. In the case of Manhattan norm, we present an algorithm working in O(n^2 log n) time, which uses an extended version of red–black trees to maintain a bipartition of a planar point set. Also in this case we provide a full version of the algorithm yielding the solutions for all size constraints k. All these procedures work in O(n) space and rely on separation results of the clusters of optimal solutions.

Exact algorithms for size constrained 2-clustering in the plane / J. Lin, A. Bertoni, M. Goldwurm. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 629(2016 May 23), pp. 80-95. [10.1016/j.tcs.2015.10.005]

Exact algorithms for size constrained 2-clustering in the plane

J. Lin
;
A. Bertoni;M. Goldwurm
2016-05-23

Abstract

We study the problem of determining an optimal bipartition {A, B}of a set X of n points in R^2, under the size constraints |A| =k and |B| = n −k, that minimizes the dispersion of points around their centroid in A and B, both in the cases of Euclidean and Manhattan norms. Under the Euclidean norm, we show that the problem can be solved in O(n k^(1/3) log^2 n) time by using known properties on k-sets and convex hulls; moreover, the solutions for all k =1, 2, ..., n/2 can be computed in O(n^2 log n) time. In the case of Manhattan norm, we present an algorithm working in O(n^2 log n) time, which uses an extended version of red–black trees to maintain a bipartition of a planar point set. Also in this case we provide a full version of the algorithm yielding the solutions for all size constraints k. All these procedures work in O(n) space and rely on separation results of the clusters of optimal solutions.
algorithms for clustering; cluster size constraints; convex hull; k-Set
Settore INF/01 - Informatica
Automi e Linguaggi Formali: Aspetti Matematici e Applicativi
Article (author)
File in questo prodotto:
File Dimensione Formato  
tcs10460.pdf

embargo fino al 05/10/2017

Descrizione: Articolo
Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 411.25 kB
Formato Adobe PDF
411.25 kB Adobe PDF Visualizza/Apri
1-s2.0-S0304397515008762-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 551.18 kB
Formato Adobe PDF
551.18 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento 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: http://hdl.handle.net/2434/426037
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact