<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div></div><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Feb 8, 2022 at 5:11 AM Kristofer Munsterhjelm <<a href="mailto:km_elmet@t-online.de">km_elmet@t-online.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Computational geometry isn't my field either, so I can't tell why a<br>
particular method will or won't work. But from what I understand, the<br>
problem of determining the volume of a general convex polytope if you<br>
only have one of its dual representations (the half-space representation<br>
or the vertex representation) is #P-hard, which is the counting analog<br>
of NP-hard.[1]<br>
<br>
So my heuristic is basically "unless you've just coincidentally solved a<br>
Millennium Prize problem, your algorithm probably won't work, or it<br>
won't be quick".<br></blockquote><div><br></div><div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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:</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">1) Either a calculation on a napkin shows that a thousand scientists missed something really obvious,</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">2) OR... those scientists know something that you don't.</div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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. </div><div><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><span style="font-family:Arial,Helvetica,sans-serif"> </span><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">But this shouldn't matter in practice. To quote another paper:<br>
<br>
> It is important to note that the algorithms differ in the input they <br>
> require; because the transformation V<->H can be prohibitively costly<br>
> for some polytopes, this can influence decisively the choice of<br>
> algorithms. Though highly depending on the concrete structure of the<br>
> polytope under consideration, one can expect tractability on <br>
> workstations for polytopes with up to 10^2 hyperplanes and 10^4 <br>
> vertices, or, 10^4 hyperplanes and 10^2 vertices, in dimension up to <br>
> 15, requiring memory up to the range of 10^2 - 10^3 MB ...<br>
So although the problem is asymptotically nasty, it starts off gentle<br>
and we shouldn't have a problem for our particular domain... though<br>
something more optimized than Python might be required for 7-10 dimensions.<br></blockquote><div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Yeah. I might try writing something in Julia (my preferred language anyway) to see if it's fast enough to be useful.</div></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">There might also be the case that some algorithm works nicely for<br>
Voronoi polytopes (or intersections of them), but not for general<br>
polytopes - that's one way your algorithm could possibly evade the<br>
"pretty much sure this is impossible" bound.</blockquote></div><div><br></div><div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.<br></div></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><font face="trebuchet ms, sans-serif">Dr. Daniel Carrera</font></div><div dir="ltr"><font face="trebuchet ms, sans-serif">Postdoctoral Research Associate</font></div><div><font face="trebuchet ms, sans-serif">Iowa State University</font></div></div></div></div></div></div></div></div></div></div></div>