1

How can I get a good description of the inner points of a polyhedron? I am trying to calculate the volume of a polyhedron by change of variables, but I can't describe the set of points of the polyhedron properly (given its vertices). I look for a description such as {(x,y,z):x+y+z<3;x<4y}.

Lorenzo Andreaus
  • 610

1 Answers1

2

For a convex polyhedron this is not so hard: any convex polyhedron is the intersection of half-spaces defined by the faces (each face lies on exactly one plane, and the polyhedron lies entirely on one side of that plane). Thus, the set of points in a convex polyhedron can be specified by $F$ linear inequalities, where $F$ is the number of faces.

For a non-convex polyhedron, I think the easiest thing to do is to express the polyhedron as a union of convex polyhedra whose pairwise intersections all have measure $0$, then apply the same procedure as above. Then you do the change of variables to each convex piece and add up your answers.

diracdeltafunk
  • 14,911
  • It will work fine, as long as I determine all the faces of the polyhedron. I just can't see how to do this, given only its vertices. In R^2 I can visualize which segments will be diagonals and which will be the edges of the (convex) polygon, but I don't know how to do it in general. – Lorenzo Andreaus Jul 24 '20 at 03:02
  • The simplest solution to this issue is as follows: any three non-colinear vertices lies on a unique plane. This plane contains a face of the polyhedron if and only if the set of vertices lies entirely on one side of the plane (you can check this algorithmically by taking dot products). – diracdeltafunk Jul 24 '20 at 03:08
  • This can almost certainly be optimized a lot, but at least this gives an $O(n^4)$ algorithm for finding a set of linear inequalities which define the convex polyhedron, where $n$ is the number of vertices. – diracdeltafunk Jul 24 '20 at 03:10