I am trying to solve some exercises of the book "Computational Geometry Algorithm and Applications, 3rd - de berg et al" of chapter 7 - Voronoi Diagrams. Unfortunately, I am not sure if I understand the following question:

Prove that for any n > 3 there is a set of n point sites in the plane such that one of the cells of Voronoi diagram(P) has n − 1 vertices

The problem is when I look at the following figure of the book: enter image description here

There are 11 site points, but I do not see any cell with 10(11-1) vertices. Does this mean I have to proof that this is not true? Or did I not understand the question correctly?

I hope that someone could show me how to solve this question.

I am not sure if this is allowed, but I also posted my question here: https://stackoverflow.com/questions/36208503/prove-that-for-any-n-3-there-is-a-set-of-n-point-sites-in-the-plane-such-that The reason that I posted the same question on stackoverflow and math.stackexchange is that someone in the comments told me that math.stackexchange is a better place for this question.


You did not understand the question correctly: The question says to show that there is SOME configuration with this property, not that every configuration has the property.

Consider the following statement: "For any open interval in the real line, there's a pair of points whose distance is rational. "

You say: In the interval $-1 < x < 1$, the points $-\pi/4$ and $\pi/4$ have a non-rational distance.

That's true, but it doesn't falsify the claim, because the points $\pm \frac{1}{2}$ have a rational distance.


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.