I've read about the algorithm in "Two algorithms for constructing a Delaunay triangulation" by D. T. Lee and B. J. Schachter, International Journal of Computer and Information Sciences, Vol. 9, No. 3, 1980. I don't quite understand how to implement the part in the merging stage where you need to find the common lower and upper tangent between the two halves. Do I need to construct a convex hull for both halves, where the vertices are sorted in clockwise or counter-clockwise order, and if so how can I manage to do that whilst recursively computing the Delaunay triangulation without exceeding O(nlogn) time. Is it maybe possible to do both simultaneously in a recursive manner, am I on the right path?