Delaunay triangulation from an EMST

Question

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 ?

Answer 1

The 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.