Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
    
Please feel free to share your ideas even if it isn't a proof yet! –  stefan Aug 25 '12 at 11:18
    
What do you mean by maximal? –  echoone Aug 25 '12 at 15:06
    
@echoone maximal means that there is no facet which is not listed. The set of facets is obviously finite. –  stefan Aug 25 '12 at 15:08
    
Ah, OK. Maybe this will help: each facet defines a hyperplane and the polytope is the inside region of the intersection of all these hyperplanes. If you have a description of $P$ and the set of facets using hyperplanes, one should be able to check if they are all there. –  echoone Aug 25 '12 at 16:02
    
I don't have a description of $P$, all I have is the information above (i.e. I know it is convex and I have all the vertices). Can you describe your idea a bit more? Right now I just don't see how this should be helpful –  stefan Aug 25 '12 at 16:08
show 10 more comments

1 Answer 1

up vote 1 down vote accepted
+50

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$.

share|improve this answer
    
First of all, thank you for the answer. Obviously every purely computational approach will take lot's of time because there is a crazy amount of facets (over 5 million, and the calculation won't stop..). But as long noone comes up with an better idea, this seems like a good approach. Thanks! –  stefan Aug 31 '12 at 12:21
    
@stefan I've added some fast-failing tests which might be of interest, and examples where they fail to guarantee that you have all facets of $P$. –  Einar Rødland Sep 1 '12 at 4:13
    
Now before the bounty expires: Thank you for your really long answer. I did not have the time to try this yet, but it seems like there will be no other possible approaches. But clearly there is need for better methods, since this will take forever. (I'm at >17e6 facets now). –  stefan Sep 3 '12 at 9:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.