Content deleted Content added
→Correctness: again, use Murtagh as source |
→The algorithm: COI edit — this is the best ref I can find on breaking ties in nearest neighbor selection (Murtagh doesn't mention this detail), but I won't complain if someone replaces it with another good reference |
||
Line 73:
If it is possible that there are multiple equal nearest neighbors to a cluster, then the algorithm requires a consistent tie-breaking rule. For instance, one may assign arbitrary index numbers to all of the clusters,
and then select (among the equal nearest neighbors) the one with the smallest index number. This rule prevents certain kinds of inconsistent behavior in the algorithm; for instance, without such a rule, the neighboring cluster {{mvar|D}} might occur earlier in the stack than as the predecessor of {{mvar|C}}.<ref>{{citation
| last1 = Eppstein | first1 = D. | author1-link = David Eppstein
| last2 = Paterson | first2 = M. S. | author2-link = Mike Paterson
| last3 = Yao | first3 = F. F. | author3-link = Frances Yao
| doi = 10.1007/PL00009293
| issue = 3
| journal = [[Discrete and Computational Geometry]]
| mr = 1432064
| pages = 263–282
| title = On nearest-neighbor graphs
| volume = 17
| year = 1997}}.</ref>
==Time and space analysis==
| |||