On 06.02.2022 20:30, Daniel Carrera wrote:

Calculating the area of a simplex is pretty easy. The trouble is in the
triangulation: the number of simplices for a fully general polytope can
increase very quickly (superpolynomially) in the number of dimensions.
That said, this is the approach some exact volume calculation methods
use. I think
https://link.springer.com/chapter/10.1007%2F978-3-0348-8438-9_6 has more
information about such algorithms.

If there's a proof that Voronoi polytopes only contain small number of
simplices (preferably according to some triangulation algorithm), then
all the better, of course! I'm not aware of any such, though. I think
finding the minimal simplex triangulation is hard for a general
polytope, though I'm not sure of that either.

-km

On Sun, Feb 6, 2022 at 4:13 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:

This is my first time thinking about computational geometry, but it seems
to me that even if you are unlucky, the number of simplices should only
grow linearly with the number of candidates. I have no idea how to find the
minimal simplex triangulation for a general polytope, but for the special
case of a convex hull, like a Voronoi cell, it doesn't look super hard:

1. Let C be a convex hull with > N+1 vertices in N dimensions.

2. Select a random set of N vertices from C.

3. Find the equation for the hyper-plane that goes through those vertices.
   Those equations have the form:

Sum{ a_k * x_k } = b

Without loss of generality, let b=1. We have N points that satisfy the
equation. That gives a linear system X*{a} = {1} where the rows of X are
the N vertices, and {a} and {1} are vectors.

4. The equations

Sum{ a_k * x_k } > 1
Sum{ a_k * x_k } < 1

Split C into two polytopes that are also convex hulls.

5. Repeat for each sub-polytope. Stop when the sub-polytope is a simplex.

Cheers,

Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University

El dom., 6 de feb. de 2022 3:00 p. m., Daniel Carrera dcarrera@gmail.com
escribió:

Recursively triangulate the boundary of C into a union beta of (N-1) dim'l
simplices.
Then let p be any point of the interior of C, and cone every member of beta
over p. Then C is the union of the resulting N dimensional simplices.

On Mon, Feb 7, 2022 at 12:16 PM Forest Simmons forest.simmons21@gmail.com
wrote:

I'm pretty new to the field, but that sounds like it should work. I can't
imagine how it wouldn't. I can already get a list of vertices from the
Polytope library and I can give those to QHull (via scipy.spatial) and
QHull can give me a list of simplices that make up the faces. Lastly, to
get p we can grab any two vertices that do not share a face and pick the
midpoint. It's hard to see how that could go wrong, but then again, what do
I know?
Kristofer pointed out that my previous algorithm wouldn't work efficiently
in cases where most sets of N+1 vertices share a face (e.g. a square base
pyramid in 3D). But your idea has no such problem as far as I can tell. I'm
sure that the general problem of dividing up a polytope into simplices is
very hard, but the specific case of a Voronoi cell honestly looks easy.

If there is a reason why it is better to divide the Voronoi cell into as
few simplices as possible, a variation of my algorithm could work well.
Instead of grabbing vertices at random you'd have to do something more
clever to avoid grabbing vertices that don't all share the same face, but
that doesn't sound hard.

Cheers,

Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University

If you are looking for minimal number of simplices in the triangulation of
an intersection of half spaces (like the feasible region of a linear
programming problem) ... it really isn't necessary to introduce new
vertices like p in the interior of a  existing convex cell ... that was
just a convenience to shorten the explanation.

For example, think of a convex polygon in a plane ... just cone the edges
from one of the existing vertices. Some of those cones will not be top
dimensional, like the cones over the two edges incident to the cone vertex,
so just throw them out or ignore them.

El lun., 7 de feb. de 2022 4:17 p. m., Daniel Carrera dcarrera@gmail.com
escribió:

On 08.02.2022 01:17, Daniel Carrera 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".

But this shouldn't matter in practice. To quote another paper:

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.

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.

(I think part of the problem lies in going from V-representation to
H-representation and back; this can take a lot of time and space.)

-km

On 08.02.2022 12:11, Kristofer Munsterhjelm wrote:

Whoops, I forgot to provide the reference link.

-km

[1] M. E. Dyer and A. M. Frieze. The complexity of computing the volume
of a polyhedron. https://doi.org/10.1137/0217060

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

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.

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

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

On 08.02.2022 13:33, Daniel Carrera wrote:

Maybe they trust themselves too much? Yes, it is odd. They don't know
how much they don't know.

Well, one could hope for something similar to the result that integer
programming is NP-hard but total unimodular integer programming is no
harder than linear programming -- that there's some additional structure
that makes it easy. But you're probably right.

Since they're talking about rationals and whether the number of bits
required to express those rationals are polynomial in the size of the
input, I doubt it's a plain counting function. But let's see...

I think it's a standard reduction strategy, i.e. that they're saying
"given this particular #P-hard problem, we can produce a polytope so
that its volume relates to the value of the output of that #P-hard
problem, in such a way that we can solve the former if we can do the
latter. Since the former is hard, so is the latter".

In this case, the problem is #Knapsack. They're being very short about
its definition (almost cryptically so), but what it means is: #KNAPSACK
is defined by a set W of integer weights {a_1, ..., a_n} and a max
weight limit b. Let O be the set of all subsets of W whose sum is at
most b. Then the desired output, i.e. the solution to the problem, is N
= |O|.

The geometric argument above this says that suppose we let x_i be 1 if
the ith weight is in our set, 0 otherwise. Then the halfspace a^Tx <= b
embodies the max limit restriction. Now let K be the intersection of
this a^Tx <= b halfspace with the unit hypercube. Then N = |K|, which is
the count of number of distinct integral points inside the resulting
polytope.

So if #KNAPSACK is #P-hard, then clearly the point count is also #P
hard. But the proof aims to show that determining the volume of he
intersection of a unit hypercube with a particular halfspace is #P-hard,
as it can be related to the point count of the polytope above. (I guess
that's where you got a bit confused.)

They proceed to define a problem #PARITY where N_0 is the number of sets
in K (defined above) with an even number of elements, and N_1 with an
odd number, and then they ask for the output N_0 - N_1 (i.e. how many
more even-length subsets than odd-length ones there are). They show this
is #P-hard.

(This is again defined in a geometric sense, |x| is the number of ones
in vector x, and since x_i is 1 iff the ith weight was chosen in
knapsack, |x| is the cardinality of the subset of W in question.)

I don't get the rest, but it seems to be roughly that they define some
function that's proportional to the area, and then a polynomial function
proportional to the volume of a particular parameterized polytope. Then
they state that if we can determine the volumes of these parameterized
polytopes, then we can determine the coefficients of the polynomial,
which is #P hard because it lets you solve #PARITY.

You'd have to go through the calculations on page 3 to check if the
volume fits the relations that the volume would (in particular the part
that goes "It is easy to show that..."). But from my glance at it, they
do seem to be talking about the actual volume (point measure/integral).

There's also Khachiyan (of ellipsoid LP algorithm fame):
doi:10.1007/978-3-642-58043-7_5 who says "it's easy to see that
computing the volume of the intersection of the unit n-dimensional cube
with a rational halfspace is NP-hard". Not so easy for me, but I have no
reason to doubt him.

This also kind of destroys our hopes that "maybe Voronoi is exempt
because there's only a few halfspaces": even a single halfspace more
than a hypercube is enough for NP-hardness (even #P-hardness as he says
later).

-km