Professor told us that brute-force construction of Voronoi diagram takes $O(n^3)$. I do not understand why not $O(n^2)$. For any given point we need to find a bisector with every other point in a set.

I draw a picture with bistros between star and all other points. And we need to do it for every point... so it results in $O(n^2)$. Tho I do not understand how we compute the actual diagram after this computation. Because it looks like too much mess. enter image description here

I cannot find the reasoning behind $O(n^3)$ complexity.

Thank you!

  • $\begingroup$ After you have drawn your bisectors, how many regions do you think there are? $\endgroup$ – Henry Mar 11 '18 at 20:43
  • $\begingroup$ @Henry well with every new bisector we should get +1 region right... so it should be 4 regions... but I am actually confused $\endgroup$ – YohanRoth Mar 11 '18 at 21:42
  • $\begingroup$ After you draw the bisectors, you iterate through them ($n-1$ iterations) to find the limits of the region around your 'star'. $\endgroup$ – N74 Mar 11 '18 at 21:54
  • $\begingroup$ Let's say you compute each individual voronoi cells. Instead of bisectors, consider half-spaces. After computing the $n-1$ half-spaces for a given point, you still have to compute their intersection, which is potentially an $(n-1)$-gon. A naive way to compute this polygon is to intersect the polygon with the next half-space, then for the $k$-th half-space you test $k-1$ intersections, resulting in an overall $O(n^2)$ complexity for a single voronoi cell. $\endgroup$ – N.Bach Mar 12 '18 at 1:14

Your Answer

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

Browse other questions tagged or ask your own question.