How to show that convex polytope is not a Voronoi cell?

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?

-
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

2 Answers

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.

-

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..

-
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