How fast can we find the nearest neighbour for a point in a set of points, given the sets Delauny Triangulation? 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.