I am reading the book "computational geometry" by Mark the Berg, Cheong, van Kreveld, Overmars
(link to the book: https://erickimphotography.com/blog/wp-content/uploads/2018/09/Computational-Geometry-Algorithms-and-Applications-3rd-Ed.pdf)
I am stuck at a part of chapter 7 which is duscussing the Voronoi Diagram, in particular page 157 of the pdf (page 149 of the book):
"Since there are $n$ sites and each Voronoi cell has at most $n−1$ vertices and edges, the complexity of $Vor(P)$ is at most quadratic. It is not clear, however, whether $Vor(P)$ can actually have quadratic complexity: it is easy to construct an example where a single Voronoi cell has linear complexity, but can it happen that many cells have linear complexity?"
Why the complexity is at most quadratic? Which formula is used to calcultate this result?
The quadratic complexity comes from multiplying $n$, the number of cells, by $n-1$, the maximum size of any cell. It's explained fairly clearly in the text.
Note that this is only an upper bound, because it may turn out that not every cell can simultaneously be close to the maximum size (spoiler alert: they can't).