Welcome to MathOverflow

Question

2

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?

flag	asked Jun 14 at 14:28 Gregor Samsa 484●1●8

5

A pity about the whole giant insect thing. – Will Jagy Jun 14 at 15:21

9

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 at 15:57

Voronoi cells of lattices are quite restricted. Did you mean that instead? – Douglas Zare Jun 15 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 at 14:12

posted as and answer then – Arthur B Jun 25 at 18:58

Arthur B · Accepted Answer · 2012-06-25 18:58:15Z UTC

7

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

answered Jun 25 at 18:58

Arthur B
847●2●8

Igor Rivin · Answer 2 · 2012-06-14 15:52:18Z UTC

0

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

answered Jun 14 at 15:52

Igor Rivin
31.1k●3●37●71

1

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 at 19:08

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.