Given a set of points $S$ and its Delauny Triangulation $DT(S)$. How fast can we find the nearest neighbour for every $x \in S$.
My idea was that each nearest neighbour-pair in $S$ shares an edge on the Delauny Triangulation, so we just need to check every edge of a point and return its nearest neighbour (=shortest edge) which can be done in constant time $\mathcal{O}(1)$?
Any hint is appreciated!
Finding the shortest of the edges requires you examine each edge; each check takes constant time, but it may take more to search the whole list. We do know that randomly distributed points give on average 6 edges per point.