[EM] Exact volume of a simplex

Daniel Carrera dcarrera at gmail.com
Tue Feb 8 04:33:05 PST 2022


On Tue, Feb 8, 2022 at 5:11 AM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

> Computational geometry isn't my field either, so I can't tell why a
> particular method will or won't work. But from what I understand, the
> problem of determining the volume of a general convex polytope if you
> only have one of its dual representations (the half-space representation
> or the vertex representation) is #P-hard, which is the counting analog
> of NP-hard.[1]
>
> So my heuristic is basically "unless you've just coincidentally solved a
> Millennium Prize problem, your algorithm probably won't work, or it
> won't be quick".
>


Indeed. This reminds me of the dozen conversations I've had with lay people
who are convinced that they came with an argument about why scientists are
obviously wrong about astronomy, climate change, or whatever. It makes me
want to tear my hair out. A couple of times I've pointed out that there are
two possibilities:

1) Either a calculation on a napkin shows that a thousand scientists missed
something really obvious,

2) OR... those scientists know something that you don't.

It baffles me that people always pick (1). If computing the volume of a
convex hull is thought to be NP-hard, I'm putting my money on (2). Also, I
have to assume that the same must be true for a Voronoi cell. I can't
imagine a reason why the volume of a Voronoi cell would be a fundamentally
different problem from the volume of a convex hull. A convex hull can have
interior points, but that has no role to play in its volume.

The paper you linked to says very clearly that the hardness proof is about
convex hulls. So I don't seen an obvious reason why it wouldn't apply to
Voronoi cells.




> But this shouldn't matter in practice. To quote another paper:
>
> > It is important to note that the algorithms differ in the input they
> > require; because the transformation V<->H can be prohibitively costly
> > for some polytopes, this can influence decisively the choice of
> > algorithms. Though highly depending on the concrete structure of the
> > polytope under consideration, one can expect tractability on
> > workstations for polytopes with up to 10^2 hyperplanes and 10^4
> > vertices, or, 10^4 hyperplanes and 10^2 vertices, in dimension up to
> > 15, requiring memory up to the range of 10^2 - 10^3 MB ...
> So although the problem is asymptotically nasty, it starts off gentle
> and we shouldn't have a problem for our particular domain... though
> something more optimized than Python might be required for 7-10 dimensions.
>

Yeah. I might try writing something in Julia (my preferred language anyway)
to see if it's fast enough to be useful.



> There might also be the case that some algorithm works nicely for
> Voronoi polytopes (or intersections of them), but not for general
> polytopes - that's one way your algorithm could possibly evade the
> "pretty much sure this is impossible" bound.



One thing that's not yet clear to me is what exactly is the #P-hard problem
in the paper. Looking at page 2, where it says "#P-hardness of Problem 1"
and the #KNAPSACK problem, I'm not entirely sure what the notation means
but I think that N = |K| is just counting the number of points from C that
are inside the polytope P. If I have understood this correctly, then I
wonder whether vol(P) means what I think it means. Sure, it means "volume",
but I can't see where it is formally defined. If it is "volume" in the
sense of counting a number of distinct points, then that problem might be
sufficiently different from the one that we are interested in that we might
avoid the hard part.


-- 
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220208/9633ec85/attachment.html>


More information about the Election-Methods mailing list