Polytopes: proving completeness of set of facets Let $P$ be a $d$-dimensional convex polytope.
$P$ is contained in $[0,1]^d$ and all vertices have only integral coefficients.
Given a set of facets of $P$, how to check that this set is maximal. i.e. that it is the set of all facets of $P$?
[update] I don't know yet if this is valid, but here's a simplification. Let's say, every facet contains the same number of vertices and this number is strictly bigger than d. Is this task easier?[/update]
[update 2] Does the general form of Eulers formula for polytopes help? It is $f_0 - f_1 + f_2 - ... + (-1)^{d-1}\cdot f_{d-1} = 1 - (-1)^d$ with $f_0$ beeing vertices, $f_1$ beeing the edges ... and $f_{d-1}$ beeing the facets. [/update 2]
As a side note: For my specific polytope, it is virtually impossible to calculate all facets by combining vertices computationally. It would take a million modern dual-core processors since the big bang to have the numbers crunched. Roughly though, could be only 10% done by now. Believe me, I've tried and my code is good. If specific information of the polytope could help you, here it is: if $n$ is an arbitrary integer, there are $n!$ vertices and the dimension is $3\cdot n\cdot(n-1)/2$.
 A: I assume you have the polytope $P$ of dimension $d$ specified by a set of points, and a set of facets $\mathcal{F}$ where each facet is a subset of $P$ spanning a $d-1$-dimensional polygon. I'm not assuming that $P\subset\{0,1\}^d$: it could be in some $d$-dimensional subspace of $\mathbb{R}^D$ or $\{0,1\}^D$ for some $D\ge d$.
For computational efficiency, I'll assume that for each vertex $v\in P$, we have a list denoted $\mathcal{F}_v$ containing all faces in $\mathcal{F}$ containing $v$.
If $P$ is a polytope, it is topologically equivalent to a $d$-ball, $B_d$, which makes its boundary (surface) $\partial P$ topologically equivalent to a $d-1$-sphere, $S_{d-1}$. Hence, if the complex (surface) induced by the facets in $\mathcal{F}$ (which I'll just denote by $\mathcal{F}$) covers the entire boundary of $P$, $\mathcal{F}$ should be a sphere and hence have no boundary. If $\mathcal{F}$ has a boundary, it does not cover all of $\partial P$; in this case, at least some of the faces of $\mathcal{F}$ that make up $F$ must contain part of the boundary of $\mathcal{F}$. Thus, what we need to do is check if any of the faces in $\mathcal{F}$ contain any boundary.
Let's take one face, $F\in\mathcal{F}$. Since $F$ is a $d-1$-dimensional polygon, its facets are $d-2$-dimensional polygons. A facet of $F$ lies on the border of $\mathcal{F}$ if and only if it is not the facet of any other facet in $\mathcal{F}$. Thus, the question is if the list of facets of $F$ we can obtain by intersecting it with other facets in $\mathcal{F}$ covers the entire boundary of $F$.
This is exactly the same question as we started with, just posed for each facet of $P$ rather than for $P$ itself, and so in one dimension lower! Hence, all we need do is run this test recursively until we get down to the vertices.
Note that the intersection of two facets $F,F'\in\mathcal{F}$ can also provide $k$-facets with lower dimension ($k<d-2$), e.g. when two facets meet at a corner, which we do not include as facets of $F$.
Example: Let $P$ be a square $ABCD$, and let $\mathcal{F}$ contain the edges $AB$, $BC$ and $CD$. For the facet $BC$, intersecting $BC$ with the two other lines provides the facets $B$ and $C$, so $BC$ is not on the border of $\mathcal{F}$. However, for the facet $AB$, only $B$ is found to be shared with another facet, so $A$ is on the border of $\mathcal{F}$.
I'm sure trying to program this would uncover technical issues I haven't thought of, but I'm pretty sure the ide should work. Speedwise, it should be proportional to the number of different sequences $(F_0,F_1,\ldots,F_{d-1})$ where $F_{d-1}\in\mathcal{F}$ and $F_k$ is a facet of $F_{k+1}$ which separates $F_k$ from some other facet of $F_{k+1}$. E.g. if the $k$-dimensional facets of $P$ each have $\nu_k$ facets, that would make the time bounded by $\nu_1\nu_2\cdots\nu_{d-1}\cdot|\mathcal{F}|$; if the facets are all simplexes, this becomes $d!\cdot|\mathcal{F}|$.

Here are a few fail-fast tests: i.e. that can indicate that the set of facets is incomplete, but is not guaranteed to do so.
Let $\mathcal{F}^{(k)}$ denote the set of $k$-facets of $P$ induced by $\mathcal{F}$: i.e. $\mathcal{F}^{(d)}=\{P\}$ is the full polytope, $\mathcal{F}^{(d-1)}=\mathcal{F}$ are the known facets, $\mathcal{F}^{(d-2)}$ are $d-2$-dimensional polytopes generated from the intersection of two facets, etc., to $\mathcal{F}^{(0)}$ which are the vertices that can be generated from intersections of facets from $\mathcal{F}$. I.e. $\mathcal{F}^{(\cdot)}$ contains all non-empty intersections of sets of facets from $\mathcal{F}$ grouped by their dimension.
If $\mathcal{F}$ contains all facets of $P$, then $\mathcal{F}^{(k)}$ should contain all $k$-facets of $P$, and the following should hold:
(1) The $0$-facets, $\mathcal{F}^{(0)}$, should contain all vertices of $P$. This is the same as saying that, for $\mathcal{F}_v$ the set of facets that contain the vertex $v\in P$, $v$ is the only vertex contained in all of them: i.e. the intersection $\cup_{F\in\mathcal{F}_v}F=\{v\}$.
(2) We can generalise (1) a bit to make it more strict. E.g. the intersections of facets in $\mathcal{F}_v$ should not only produce the $0$-facet $\{v\}$, but also a number of $1$-facets, $2$-facets, etc.: at least two of each, but if facets are themselves convex polytopes there must be more of them.
(3) If $f_k=\dim\mathcal{F}^{(k)}$, as in the original problem proposal, the Euler characteristic $\chi(\mathcal{F})=f_0-f_1+\cdots+(-1)^df_d$ should be equal to $\chi(P)=1$ (which is true since $P$ is contractible).
Examples where these fail are:
(1a) A tetrahedron with $\mathcal{F}$ lacking one of the sides.
(1b) Let $P$ be an octahedron with vertices $R=[1,0,0]$, $L=[-1,0,0]$, $F=[0,1,0]$, $B=[0,-1,0]$, $U=[0,0,1]$, $D=[0,0,-1]$ (right, left, forward, backward, up, down): I'm sure you can embed this in $\{0,1\}^D$ for some $D$. While $P$ has 8 faces, we let $\mathcal{F}=\{RFU,LBU,RBD,LFD\}$. The six vertices all occur as intersections of faces from $\mathcal{F}$: we'd have to look at the edges to see that $\mathcal{F}^{(\cdot)}$ is incomplete.
(2) An icosahedron with $\mathcal{F}$ lacking one side.
(3) Let $P$ be a cube, and let $\mathcal{F}$ consist only of two opposing sides. Since all intersections of faces in $\mathcal{F}$ are empty, we get $f_0=f_1=0$, $f_2=2$, $f_3=1$ which makes $\chi(\mathcal{F})=1$.
A: Assuming the $D-1$-faces do not have common interior points. Otherwise, you'll need to do some polytope subtraction before applying this method.
Since it is a convex polytope, its centroid is guaranteed to be within it. For each $D-1$-face, you can project all the vertices and $D-2$-edges onto a hollow unit $D-1$-sphere around the centroid, and calculate the total resulting $D-1$-surface-volume. If the total $D-1$-surface-volume is less than that of a hollow unit $D-1$-sphere, you have a hole. The projection and volume calculation could be done with a spherical coordinate integral $\oint\limits_{D-1\text{-face}} d\vec\phi$, which should decompose into lower dimensions down to ordinary vertices. The hard part is, of course, a general closed form for such a decomposition, although you could define the whole calculation recursively and functionally (say, in Haskell) and leave the execution to a computer.
Making this a community wiki since many details are not implemented.
