کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435272 689889 2016 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Exact algorithms for size constrained 2-clustering in the plane
ترجمه فارسی عنوان
الگوریتم های دقیق برای اندازه محدود 2 خوشه بندی در هواپیما
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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(nk3log2⁡n) 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(n2log⁡n)O(n2log⁡n) time. In the case of Manhattan norm, we present an algorithm working in O(n2log⁡n)O(n2log⁡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)O(n) space and rely on separation results of the clusters of optimal solutions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 629, 23 May 2016, Pages 80–95
نویسندگان
, , ,