Maximizing the maximum degree in ordered nearest neighbor graphs
Péter Ágoston, Adrian Dumitrescu, Арсений Сагдеев, Karamjeet Singh, Ji Zeng · Computational Geometry · 2025
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 R d , there exists an order such that the corresponding ordered Nearest Neighbor Graph has maximum degree at least log n / ( 4 d ) . Apart from the 1 / ( 4 d ) 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 Ω ( log n / log log n ) .