# What is the most efficient way to "look up" a face in the face lattice of a polyhedron?

Say I have a polyhedron p with face lattice L = p.face_lattice(). I want to define x as the element of L defined as the convex hull of vertices <0 1 3> of p. What is the most efficient way to define x?

For example, consider

sage: p = polytopes.simplex(3)
sage: for v in p.vertices():
print '\tIndex {}:'.format(v.index()), v
....:
Index 0: A vertex at (0, 0, 0, 1)
Index 1: A vertex at (0, 0, 1, 0)
Index 2: A vertex at (0, 1, 0, 0)
Index 3: A vertex at (1, 0, 0, 0)


We see that p has four vertices.

The vertices indexed by 0, 1, and 3 are the vertices of a face of p. This is confirmed:

sage: L = p.face_lattice()
sage: list(L)
[<>,
<0>,
<1>,
<2>,
<3>,
<0,1>,
<0,2>,
<1,2>,
<0,3>,
<1,3>,
<2,3>,
<0,1,2>,
<0,1,3>,
<0,2,3>,
<1,2,3>,
<0,1,2,3>]


I want to define x as the face in p.face_lattice() given by these vertices. Of course, I could do this by hand with x = list(L)[12], but I want a way to automate this.

edit retag close merge delete

Please provide a polyhedron p so that other users have a starting point to try and answer your question.

( 2016-08-16 17:34:15 -0500 )edit

@slelievre Thanks for the suggestion. I've updated my question with an example.

( 2016-08-16 18:16:25 -0500 )edit

Sort by » oldest newest most voted

This is a very natural question, but unfortunately at the moment the answer is a bit complicated. This answer assumes sage 9.1+:

As this is a combinatorial property, you can go into CombinatorialPolyhedron, which is now a method of a polyhedron. There you can obtain the answer via the face iterator. The face iterator iterates through all faces of the polyhedron with a depth-first search. Of course you could just iterate until you what you are looking for, but the iterator can also be manipulated. For this I need to explain a bit, how it works. Assume for now that the iterator is in non-dual mode, it generates all faces from the facets.

The iterator yields first all facets. Then it inductively yields all faces of the first facet (treating it as it's own polyhedron) and then marks it as being visited. Then it yields all faces of the second facet, but the faces contained in the first facet. After that it marks the second facet as being visited and so on.

Now in our situation it might happen, that the first facet does not contain the goal face. Then we want to mark it immediately as being visited. Likewise we proceed with all facets. The below code will proceed like this for the ridges and so on, which might be easier to adapt, when you need different properties.

You might observe that in this particular situation it suffices to mark the correct facets as visited.

Now, if your polyhedron contains many facets but few vertices, generating all faces from the facets might be a bad idea. This is why the iterator can work in dual mode as well. In this case you can decide to skip supfaces instead of subfaces.

As mentioned before, this is a natural question and eventually I think there should be a method like find-join-of-vertices or find-meet-of-facets.

The following should work (it assumes that the face really does exist, otherwise you need to alter the termination condition of the while loop to fit your need):

from sage.geometry.polyhedron.face import combinatorial_face_to_polyhedral_face
def is_subset(a,b):
return all(x in b for x in a)

def obtain_face(P, *indices):
indices = tuple(indices)
C = P.combinatorial_polyhedron()
it = C.face_iter()

# Let f be the first facet in non-dual mode or the first vertex in dual mode.
f = next(it)

while f.ambient_V_indices() != indices:
if not it.dual:
# Skipping faces unless our goal face is a subface.
if not is_subset(indices, f.ambient_V_indices()):
it.ignore_subfaces()
else: # the face iterator starts with the vertices
# Skipping faces unless our goal face is a supface.
if not is_subset(f.ambient_V_indices(), indices):
it.ignore_supfaces()
f = next(it)

# f is now the combinatorial face we where looking for (assuming it exists).
# Obtain a polyhedral face from it.
return combinatorial_face_to_polyhedral_face(P, f)


Then you get:

sage: P = polytopes.cross_polytope(4)
sage: f = obtain_face(P, 2,4,6)
sage: f.ambient_V_indices()
(2, 4, 6)
sage: f
A 2-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 3 vertices
sage: P = polytopes.hypercube(3)
sage: f = obtain_face(P, 0,1,5,6)
sage: f.ambient_V_indices()
(0, 1, 5, 6)
sage: f
A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices


This should be pretty fast. Note, that no options of the face iterator are exposed in the polyhedron and one has to go into combinatorial polyhedron (skipping subfaces or supfaces is crucial, because we only want one depth search and find our face immediately).

The the subset check function is not optimized deliberately.

more

Not very user friendly :-)

( 2020-04-23 11:17:26 -0500 )edit

Yes, I noticed. It wasn't until JP pointed me to this post that I realized that this would be a nice thing to have. This is all very much work in progress and it reminds me that more stuff of combinatorial polyhedron should be exposed. I might be about the only person aware of the methods ignore_subfaces and ignore_supfaces.

( 2020-04-23 15:09:03 -0500 )edit

I edited the answer to explain what the code is doing.

( 2020-05-11 14:16:32 -0500 )edit

The following works for me:

TYPES = ( int, sage.rings.integer.Integer )

def get_face( P, verticesInput ):
"""Here, <P> is a polyhedron,
and the <verticesInput> are a list of true vertices of the polyhedron.
Then we search for a face of the polyhedron having the given <verticesInput>
matching the own vertices. If found, we return it. If not we return None.
"""

verticesP = P.vertices()
verticesSetInput = set( [ verticesP[ v ] if type(v) in TYPES else v
for v in verticesInput ] )

if len( verticesInput ) != len( verticesSetInput ):
return

for f in P.face_lattice():
if set( f.vertices() ) == verticesSetInput:
return f

P = polytopes.dodecahedron()
# test
for data in ( [0..3], [0..4], [0..5], [15..19], {8,15}, (7,) ):
f = get_face( P, data )
if f:    print "data = %s --> FOUND FACE %s" % ( data, f )
else:    print "data = %s --> NO SUCH FACE"  % ( data )


It gives:

data = [0, 1, 2, 3] --> NO SUCH FACE
data = [0, 1, 2, 3, 4] --> FOUND FACE <0,1,2,3,4>
data = [0, 1, 2, 3, 4, 5] --> NO SUCH FACE
data = [15, 16, 17, 18, 19] --> FOUND FACE <15,16,17,18,19>
data = set([8, 15]) --> FOUND FACE <8,15>
data = (7,) --> FOUND FACE <7>

more