TY - GEN
T1 - Optimal algorithms for complete linkage clustering in d dimensions
AU - Krznaric, Drago
AU - Levcopoulos, Christos
PY - 2002
Y1 - 2002
N2 - It is shown that the complete linkage clustering of n points in R-d, where d greater than or equal to 1 is a constant, can be computed in optimal O(nlogn) time and linear space, under the L-1 and L-infinity-metrics. Furthermore, for every other fixed L-t-metric, it is shown that it can be approximated within an arbitrarily small constant factor in O(nlogn) time and linear space.
AB - It is shown that the complete linkage clustering of n points in R-d, where d greater than or equal to 1 is a constant, can be computed in optimal O(nlogn) time and linear space, under the L-1 and L-infinity-metrics. Furthermore, for every other fixed L-t-metric, it is shown that it can be approximated within an arbitrarily small constant factor in O(nlogn) time and linear space.
KW - multidimensional
KW - optimal algorithms
KW - complete linkage clustering
KW - approximation algorithms
KW - hierarchical clustering
U2 - 10.1016/S0304-3975(01)00239-0
DO - 10.1016/S0304-3975(01)00239-0
M3 - Paper in conference proceeding
VL - 286
SP - 139
EP - 149
BT - Theoretical Computer Science
PB - Elsevier
ER -