2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am using Bowyer–Watson algorithm here. Can you please explain a bit more about how If I do randomize the points, the worst case is practically impossible to happen? I mean how randomization helps avoiding the worst case? can you give a small example on what would happen if I randomize the points and if I dont? @Simon $\endgroup$ – user5411115 Nov 28 '16 at 4:49
  • $\begingroup$ Think about the non randomized algorithm. The average time is is O(n log n) but the worst is O(n^2). This means most possible inputs are fast but some are slow. "average runtime" means the time it takes to solve a random input. But the thing is in the real world the input is probably not random. The input comes from some user. So it might be the case that your actual input is always one of those with bad performance. You, the algorithm designer, have no control over that. By randomising yourself you prevent that and the average runtime becomes truly average. $\endgroup$ – Simon Nov 28 '16 at 6:34
  • $\begingroup$ Actually, I have a little bit confusion about the random input. Say, In case of voronoi diagram, the input is a list of points (x,y) in 2D. For randomized input, does it mean the input is randomly generated or after taking any input it is randomly shuffled and then used in the program? Or does it mean anything else? @Simon $\endgroup$ – user5411115 Nov 28 '16 at 7:37
  • $\begingroup$ Yes, generally these two versions are different. But in the case of the voronoi/delauny algorithm either version of randomization works to get you the desired average performance. $\endgroup$ – Simon Nov 28 '16 at 7:39
  • $\begingroup$ But of course you can only do the shuffling. The points in your input are given by a user and are out of your control. The worst case can still happen with shuffling , but only by very bad luck. It can not be triggered by bad input in itself. $\endgroup$ – Simon Nov 28 '16 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.