Nearest-neighbor chain algorithm: Difference between revisions

Revision as of 06:31, 25 January 2022

Revision as of 06:09, 16 May 2022

Line 55:

==The algorithm==

[[File:Nearest-neighbor chain algorithm animated.gif|frame|300px|alt=Animated execution of Nearest-neighbor chain algorithm|Animation of the algorithm using Ward's distance. Black dots are points, grey regions are larger clusters, blue arrows point to nearest neighbors, and the red bar indicates the current chain. For visual simplicity, when a merge leaves the chain empty, it continues with the recently merged cluster.]]

Intuitively, the nearest neighbor chain algorithm repeatedly follows a chain of clusters {{math|''A'' → ''B'' → ''C'' → ...}} where each cluster is the nearest neighbor of the previous one, until reaching a pair of clusters that are mutual nearest neighbors.<ref name="murtagh-tcj">{{citation

| last = Murtagh | first = Fionn