Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs

For an ordered point set in a Euclidean space or, more generally, in an abstract metric space, the ordered Nearest Neighbor Graph is obtained by connecting each of the points to its closest predecessor by a directed edge. We show that for every set of $n$ points in ${\mathbb{R}}^d$, there exists an order such that the corresponding ordered Nearest Neighbor Graph has maximum degree at least $\log n\mathrm{/}(4d)$. Apart from the $1\mathrm{/}(4d)$ factor, this bound is the best possible. As for the abstract setting, we show that for every $n$-element metric space, there exists an order such that the corresponding ordered Nearest Neighbor Graph has maximum degree $\mathrm{\Omega }(\sqrt{\log n\mathrm{/}\log \log n})$.