Ask Your Question
1

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

asked 2016-08-16 04:06:34 -0500

done_with_fish gravatar image

updated 2016-08-16 18:16:58 -0500

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 flag offensive close merge delete

Comments

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

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

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

done_with_fish gravatar imagedone_with_fish ( 2016-08-16 18:16:25 -0500 )edit

2 answers

Sort by ยป oldest newest most voted
2

answered 2020-04-23 11:04:54 -0500

Jonathan Kliem gravatar image

updated 2020-05-11 14:16:01 -0500

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.

edit flag offensive delete link more

Comments

Not very user friendly :-)

vdelecroix gravatar imagevdelecroix ( 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.

Jonathan Kliem gravatar imageJonathan Kliem ( 2020-04-23 15:09:03 -0500 )edit

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

Jonathan Kliem gravatar imageJonathan Kliem ( 2020-05-11 14:16:32 -0500 )edit
0

answered 2017-07-19 15:27:53 -0500

dan_fulea gravatar image

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>
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-08-16 04:06:34 -0500

Seen: 700 times

Last updated: May 11