The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Optimal algorithms for complete linkage clustering in d dimensions

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2002

Language

English

Pages

139-149

Publication/Series

Theoretical Computer Science

Volume

286

Issue

1

Document type

Conference paper

Publisher

Elsevier

Topic

  • Computer Science

Keywords

  • multidimensional
  • optimal algorithms
  • complete linkage clustering
  • approximation algorithms
  • hierarchical clustering

Status

Published

ISBN/ISSN/Other

  • ISSN: 0304-3975