4
$\begingroup$

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?

$\endgroup$
5
  • 7
    $\begingroup$ A pity about the whole giant insect thing. $\endgroup$
    – Will Jagy
    Jun 14, 2012 at 15:21
  • 9
    $\begingroup$ 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? $\endgroup$
    – Arthur B
    Jun 14, 2012 at 15:57
  • $\begingroup$ Voronoi cells of lattices are quite restricted. Did you mean that instead? $\endgroup$ Jun 15, 2012 at 10:57
  • 1
    $\begingroup$ @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! $\endgroup$ Jun 15, 2012 at 14:12
  • $\begingroup$ posted as and answer then $\endgroup$
    – Arthur B
    Jun 25, 2012 at 18:58

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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.) $\endgroup$ Jun 14, 2012 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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