Voronoi diagram implementation using Delaunay Triangulation

Question

I am trying to implement Voronoi diagram using Delaunay Triangulation as the dual of Delaunay Triangulation is Voronoi diagram. I have a little bit confusion about the time complexity of it considering two different approach. One is, if I insert the points in Delaunay triangulation at a random sorted order and if not. Does the random ordering of input before inserting into triangulation ensures a better $O(n\log n)$ running time all the times? what is the main difference between these two approaches?

Answer 1

It depends on the details of your implementation. The easiest methods have a worst case complexity of $O(n^2)$, but average $O(n \log n)$.

If you do randomize the points, the worst case is practically impossible to happen. But without randomization a malicious user of your code could carefully craft an instance that triggers the worst case. Therefore doing the randomization yourself is considered "safer" than just relying on the input to be "not too bad". Randomization does not improve the runtime for nice inputs.

It is worth noting that it is possible to write a fully deterministic version of the algorithm with $O(n\log n)$ worst case runtime. But that makes the code quite a bit more complex, so it might well not be worth the trouble.