IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca

IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.

AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.

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.

Powered by IRIS-about IRIS-Utilizzo dei cookie

 Copyright © 2021