Nearest-neighbor chain algorithm: Difference between revisions

Revision as of 17:49, 31 October 2016

Revision as of 20:45, 31 October 2016

Line 74:

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>For this tie-breaking rule, and an example of how tie-breaking is needed to prevent cycles in the nearest neighbor graph, see {{citation|contribution=Figure&nbsp;20.7|page=244|title=Algorithms in Java, Part 5: Graph Algorithms|first=Robert|last=Sedgewick|authorlink=Robert Sedgewick (computer scientist)|edition=3rd|publisher=Addison-Wesley|year=2004|isbn=0-201-36121-3}}.</ref>

| 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==