Fast Algorithms for Complete Linkage Clustering

Abstract.

It is shown that the complete linkage clustering of n points can be computed in O(n log ² n) time. Furthermore, it is shown that the complete linkage clustering can be approximated within an arbitrarily small constant factor in O(n log n) time.

Similar content being viewed by others

Improved Analysis of Complete-Linkage Clustering

Article 06 February 2017

A Density-Sensitive Hierarchical Clustering Method

Article 28 September 2018

Versatile Linkage: a Family of Space-Conserving Strategies for Agglomerative Hierarchical Clustering

Article 16 July 2019

Author information

Authors and Affiliations

1. Department of Computer Science, Lund University, Box 118, S-221 00 Lund, Sweden drago@dna.lth.se christos@dna.lth.se, , , , , , SE

   D. Krznaric & C. Levcopoulos

Authors

1. D. Krznaric
   View author publications

   You can also search for this author in PubMed Google Scholar

2. C. Levcopoulos
   View author publications

   You can also search for this author in PubMed Google Scholar

Additional information

Received September 18, 1995, and in revised form April 17, 1997.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Krznaric, D., Levcopoulos, C. Fast Algorithms for Complete Linkage Clustering . Discrete Comput Geom 19, 131–145 (1998). https://doi.org/10.1007/PL00009332

Download citation

• Issue Date: January 1998

• DOI: https://doi.org/10.1007/PL00009332

Keywords

• Constant Factor
• Fast Algorithm
• Complete Linkage
• Linkage Cluster
• Complete Linkage Cluster