MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a combinatorial type of a convex polytope, what techniques are available for showing that it cannot be realized as a Voronoi cell of some point system?

share|cite|improve this question
A pity about the whole giant insect thing. – Will Jagy Jun 14 '12 at 15:21
Pardon my naivete, but if pick a point inside the polytope and reflect it across every facets, isn't your polytope the voronoi cell of that point? Can you give an example of a convex polytope that isn't? – Arthur B Jun 14 '12 at 15:57
Voronoi cells of lattices are quite restricted. Did you mean that instead? – Douglas Zare Jun 15 '12 at 10:57
@Arthur B: You are absolutely right, of course. I am mildly shocked by this false belief I carried with me for a long time, and how easily it could be refuted. Since I am normally not working with Voronoi diagrams, I never questioned it. A couple of days ago I decided to try out MO and thought, well, this would make for an interesting question... but apparently not. So thanks for your comment! – Gregor Samsa Jun 15 '12 at 14:12
posted as and answer then – Arthur B Jun 25 '12 at 18:58
up vote 10 down vote accepted

Every (non-flat) convex polytope is the Voronoi cell of a point in a set of points. Constructive proof: pick a point inside the polytope, and build its symmetric reflection along every facet of the polytope.

share|cite|improve this answer

There is this paper of Boissonnat and Karavelas where they prove bounds on the combinatorial convexity of Voronoi cells. Presumably if your polytope does not satisfy the bound, it is not a Voronoi cell..

share|cite|improve this answer
Of course, the bound has to depend on the number of points, so I don't see how this can work. (From skimming the paper, it appears that the best bound is Theta(n^ceiling(d/2)), where n is the number of points and d is the dimensionality of space, which is not unexpected.) – Darsh Ranjan Jun 14 '12 at 19:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.