Assume you know the Euclidean Minimum Spanning Tree of a set of $n$ 2D points (in general position).
Is there an efficient way (faster than $O(n \log n)$ operations) to obtain the Delaunay triangulation of these points ?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityThe Wikipedia article states, that:
the Delaunay triangulation can be constructed from the Euclidean minimum spanning tree in the near-linear time bound $O(n\log ^{*}n)$, where $\log ^{*}$ denotes the Iterated logarithm.
This article refers to the paper, where you can find a randomized algorithm for the problem you're interested in.