کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435272 | 689889 | 2016 | 16 صفحه PDF | دانلود رایگان |
We study the problem of determining an optimal bipartition {A,B}{A,B} of a set X of n points in R2R2, under the size constraints |A|=k|A|=k and |B|=n−k|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(nk3log2n) time by using known properties on k -sets and convex hulls; moreover, the solutions for all k=1,2,…,⌊n/2⌋k=1,2,…,⌊n/2⌋ can be computed in O(n2logn)O(n2logn) time. In the case of Manhattan norm, we present an algorithm working in O(n2logn)O(n2logn) 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)O(n) space and rely on separation results of the clusters of optimal solutions.
Journal: Theoretical Computer Science - Volume 629, 23 May 2016, Pages 80–95