# Why brute-force Voronoi diagram computation takes $O(n^3)$

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.

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

Thank you!

• After you have drawn your bisectors, how many regions do you think there are? – Henry Mar 11 '18 at 20:43
• @Henry well with every new bisector we should get +1 region right... so it should be 4 regions... but I am actually confused – YohanRoth Mar 11 '18 at 21:42
• After you draw the bisectors, you iterate through them ($n-1$ iterations) to find the limits of the region around your 'star'. – N74 Mar 11 '18 at 21:54
• 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. – N.Bach Mar 12 '18 at 1:14