The diameter of nearest neighbor graphs
David Eppstein · eScholarship (California Digital Library) · 1992
Any connected plane nearest neighbor graph has diameter #(n 1/6 ). This bound generalizes to #(n 1/3d ) in any dimension d. For any set of n points in the plane, we define the nearest neighbor graph by selecting a unique nearest neighbor for each point, and adding an edge between each point and its neighbor. This is a directed graph with outdegree one; thus it is a pseudo-forest. Each component of the pseudo-forest is a tree, with a length-two directed cycle at the root. As with minimum spanning trees, the maximum degree in a nearest neighbor graph is five. Monma and Suri [1] showed that, conversely, any tree with vertex degree at most five is the minimum spanning tree of some point set; thus minimum spanning tree topologies are exactly characterized by their degrees. Paterson and Yao [2] considered the corresponding question for nearest neighbor graphs. They showed that a tree with depth D can have at most O(D 9 ) vertices. Thus unlike minimum spanning trees, nearest neighbor...