[[Complete-linkage clustering|Complete-linkage]] or furthest-neighbor clustering is a form of agglomerative clustering that usesdefines the dissimilarity between clusters to be the maximum distance between any two points from the two clusters. as the dissimilaritySimilarly, and similarly average-distance clustering uses the average pairwise distance as the dissimilarity. Like Ward's distance, these two forms of clustering obey a formula of Lance-Williams type:. inIn complete linkage, the distance <math>d(A\cup B,C)</math> is the average of the distances <math>d(A,C)</math> and <math>d(B,C)</math> plus a positive correction term,. while forFor average distance, it<math>d(A\cup B,C)</math> is just a weighted average of the distances <math>d(A,C)</math> and <math>d(B,C)</math>.<ref name="mirkin"/><ref name="lance-williams"/> Thus, in both of these cases, the distance is reducible.
Unlike Ward's method, these two forms of clustering do not have a constant-time method for computing distances between pairs of clusters. Instead it is possible to maintain an array of distances between all pairs of clusters, using the Lance–Williams formula to update the array as pairs of clusters are merged,. inMaintaining this array over the course of the clustering algorithm takes time and space {{math|''O''(''n''<sup>2</sup>)}}. The nearest-neighbor chain algorithm may be used in conjunction with this array of distances to find the same clustering as the greedy algorithm for these cases. inIts total time and space, using this array, is also {{math|''O''(''n''<sup>2</sup>)}}.<ref name="gm07"/>
The same {{math|''O''(''n''<sup>2</sup>)}} time and space bounds can also be achieved byin a different andway, by more generala technique that overlays a [[quadtree]]-based priority queue data structure on top of the distance matrix and uses it to perform the standard greedy clustering algorithm. This quadtree method is more general, avoidingas theit needworks even for reducibility,clustering methods that are not reducible.<ref name="e-jea"/> butHowever, the nearest-neighbor chain algorithm matches its time and space bounds while using simpler data structures.<ref name="gm07">{{citation
