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!