4
$\begingroup$

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

$\endgroup$
15
  • $\begingroup$ Please feel free to share your ideas even if it isn't a proof yet! $\endgroup$
    – stefan
    Aug 25, 2012 at 11:18
  • $\begingroup$ What do you mean by maximal? $\endgroup$
    – echoone
    Aug 25, 2012 at 15:06
  • $\begingroup$ @echoone maximal means that there is no facet which is not listed. The set of facets is obviously finite. $\endgroup$
    – stefan
    Aug 25, 2012 at 15:08
  • $\begingroup$ 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. $\endgroup$
    – echoone
    Aug 25, 2012 at 16:02
  • $\begingroup$ 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 $\endgroup$
    – stefan
    Aug 25, 2012 at 16:08

2 Answers 2

1
+50
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – stefan
    Aug 31, 2012 at 12:21
  • $\begingroup$ @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$. $\endgroup$ Sep 1, 2012 at 4:13
  • $\begingroup$ 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). $\endgroup$
    – stefan
    Sep 3, 2012 at 9:14
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .