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?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Every (nonflat) 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.. 

