GEOMETRIC CLUSTERINGS

被引：54

作者：

CAPOYLEAS, V

ROTE, G

WOEGINGER, G

机构：

[1] COURANT INST,NEW YORK,NY 10012

[2] GRAZ TECH UNIV,INST MATH,A-8010 GRAZ,AUSTRIA

来源：

JOURNAL OF ALGORITHMS | 1991年 / 12卷 / 02期

关键词：

D O I：

10.1016/0196-6774(91)90007-L

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A k-clustering of a given set of points in the plane is a partition of the points into k subsets ("cluster"). For any fixed k, we can find a k-clustering which minimizes any monotone function of the diameters or the radii of the clusters in polynomial time. The algorithm is based on the fact that any two clusters in an optimal solution can be separated by a line. © 1991.

引用

页码：341 / 356

页数：16

共 17 条

[1]

[Anonymous], 1950, ACTA SCI MATH

[2]

ASANO T, 1988, 4TH P ANN ACM S COMP, P252

[3] POWER DIAGRAMS - PROPERTIES, ALGORITHMS AND APPLICATIONS [J].