"look up" a face in the face lattice of a polyhedron

[kliem]

We implement two methods that look up a face in the face lattice of a polyhedron:

• meet_of_Vrep -- the smallest face containing specified Vrepresentatives
• join_of_Hrep -- the largest face contained specified facets

This allows an easy answer for ​https://ask.sagemath.org/question/34485/what-is-the-most-efficient-way-to-look-up-a-face-in-the-face-lattice-of-a-polyhedron/#50965

Depends on #31834

CC: @jplab @LaisRast @videlec @yuan-zhou

Component: geometry

Keywords: polyhedron, faces, meet, join

Author: Jonathan Kliem

Branch/Commit: 8190917

Reviewer: Yuan Zhou, Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/29683

[kliem]

Branch: pubic/29683

[kliem]

Changed branch from pubic/29683 to public/29683

[kliem]

Commit: 521f9e0

[kliem]

Last 10 new commits:

295039a	documentation
d36da4a	coverage and small improvement
2d0f0d9	method `reset` for the face iterator
6d99a4c	typo
5711f6b	method `ignore_subsets`
f6633bd	method current and fix for reset
e8c17c3	join_of_Vrep and meet_of_facets for face iterator
b371a73	expose in combinatorial_polyhedron
954b5c8	raise index error for index error
521f9e0	expose in Polyhedron_base

[kliem]

comment:3

There are failing tests. I would wait until the dependices are taken care of to make things work again.

[kliem]

New commits:

19d2742	join_of_Vrep and meet_of_facets for face iterator
c5c17ff	account for changes in the newest develop
7a4b950	expose in combinatorial_polyhedron
f108b06	raise index error for index error; fix doctests
a69ba9f	expose in Polyhedron_base
a6f53af	fix doctests

[kliem]

Changed commit from 521f9e0 to a6f53af

[kliem]

Changed branch from public/29683 to public/29683-reb

[kliem]

comment:6

I want to redesign some of the setup before making everything more complicated.

More precisely, creating strucutures face_struct and faces_list_struct that take care of the details. Then this overly long argument list of get_next_level will just reduce to three arguments or so. This would also make future changes easier including the transition to bitsets.pxi.

[kliem]

Changed commit from a6f53af to 7e0a25e

[kliem]

New commits:

2a14433	join_of_Vrep and meet_of_facets for face iterator
530d85c	expose in combinatorial_polyhedron
73a8be1	raise index error for index error; fix doctests
c7ce411	expose in Polyhedron_base
7e0a25e	fix doctests

[kliem]

Changed dependencies from #29681 to none

[kliem]

Changed branch from public/29683-reb to public/29683-reb2

[mkoeppe]

comment:8

Some quick comments:

• "The offset is taken correctly" - what's that?
• Change "reseted" to "reset"
• "In case of an unbounded polyhedron" -> "In the case ..."

[kliem]

comment:9

I discovered a bug by accident:

sage: P = polytopes.permutahedron(3, backend='cdd')                                                                                                                                 
sage: [x.ambient_Hrepresentation() for x in P.facets()]                                                                                                                             
[(An inequality (1, 1, 0) x - 3 >= 0, An inequality (1, 0, 1) x - 3 >= 0),
 (An inequality (1, 1, 0) x - 3 >= 0, An inequality (1, 0, 0) x - 1 >= 0),
 (An inequality (1, 1, 0) x - 3 >= 0, An inequality (0, 1, 1) x - 3 >= 0),
 (An inequality (1, 1, 0) x - 3 >= 0, An inequality (0, 1, 0) x - 1 >= 0),
 (An inequality (1, 1, 0) x - 3 >= 0, An inequality (0, 0, 1) x - 1 >= 0),
 (An inequality (1, 1, 0) x - 3 >= 0, An equation (1, 1, 1) x - 6 == 0)]

The problem is that the backend cdd doesn't put equations in a stable place, which my code assumed. It depends whether you initialize from Vrep or from Hrep I guess.

[kliem]

comment:74

Replying to @yuan-zhou:

It's still not all correct in the corner cases.

sage: P = Polyhedron(vertices=[[1,0]], lines=[[1,1]])                                                      
sage: P.Vrepresentation()                                                                                  
(A line in the direction (1, 1), A vertex at (1, 0))
sage: P.join_of_Vrep(0)                                                                                    
A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 line

and

sage: R = Polyhedron(vertices=[[1,0]], rays=[[1,1]])                                                       
sage: R.Vrepresentation()                                                                                  
(A vertex at (1, 0), A ray in the direction (1, 1))
sage: R.join_of_Vrep(1)                                                                                    
A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray

Expected to have ValueError: the join is not well-defined for both.

With one more vertex, it's correct though:

sage: Q = Polyhedron(vertices=[[1,0], [0,1]], lines=[[1,1]])                                               
sage: Q.Vrepresentation()                                                                                  
(A line in the direction (1, 1), A vertex at (-1, 0), A vertex at (1, 0))
sage: Q.join_of_Vrep(0)
ValueError: the join is not well-defined

It's consistent. Still one can argue about whether it should be changed.

What you are proposing is the following: Given a bunch of indices. If there are in the far face, throw an error.

Current behavior is the following (and I also wasn't aware of this, after all the ticket has been sitting there for a year): Given no indices, return the empty face. Otherwise, intersect all facets that contain all given indices. If that is contained in the far face, throw an error.

In the first of your cases, there is no facet. In the second case, the only facet does not contain the index. In the third case, both facets contain the line and thus the join is really not defined.

A different example where currently everything works out is the following:

sage: P = Polyhedron(vertices=[[0,1],[1,0]], rays=[[0,1],[1,0]])                                                                                                                    
sage: P.Vrepresentation()                                                                                                                                                           
(A ray in the direction (0, 1),
 A vertex at (0, 1),
 A ray in the direction (1, 0),
 A vertex at (1, 0))
sage: for i in range(4): 
....:     P.join_of_Vrep(i) 
....:                                                                                                                                                                               
A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray
A 0-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex
A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray
A 0-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex

There is always exactly one face containing each ray. It even makes sense when you consider the lattice of the cone (or add the far face). The ray is of course a face of it's own there. However, there is a unique smallest face in the original polyhedron that contains it.

I think the current behavior makes sense. You could give me a bunch of rays of a large polyhedron and ask me, what's the smallest face containing them. As long as this is well-defined, you can except to get an answer and not an error. It's like computing gcd and lcm. It tries to find an answer for you and only fails if those two numbers do not have a unique meet or join.

[yuan-zhou]

comment:75

Actually, I'm not considering combinatorial polyhedra, far face, etc. at all. Instead, I'm looking from a geometric point of view.

In the examples above, I see "A line in the direction (1, 1)" as l = Polyhedron(lines=[(1,1)]), and "A ray in the direction (1, 1)" as r = Polyhedron(rays=[(1,1)]). Recall that for a geometric polyhedron (of Polyhedron_base class), it is a face of itself, and the empty polyhedron is also a face.

None of the faces of P (including itself) contains l. Similarly, none of the faces of Q (including itself) contains r. Thus, I expect an error in the first two examples.

None of the faces of Q contains l. Therefore, the third example returns an error.

[kliem]

comment:76

I don't think one should see "A line in the direction (1, 1)" as l = Polyhedron(lines=[(1,1)]), because whenever you don't specify vertices, but rays or lines, then the vertex (0,0) is added.

P contains the line and not l, because l is the line and the vertex (0,0).

No, the third example returns an error, because both edges of Q contain the line, but not a vertex. So it is not well-defined.

Edit: Maybe rather say 1-faces instead of edges. There are two 1-faces of Q that contain the lines, but no 0-face of Q contains the line.

[yuan-zhou]

comment:77

Replying to @kliem:

I don't think one should see "A line in the direction (1, 1)" as l = Polyhedron(lines=[(1,1)])

Aha! That explains everything.

[kliem]

comment:79

Thank you.

That part with the implicit vertex is super confusing...

[kliem]

Changed commit from 110228e to 644a803

[kliem]

Changed branch from public/29683-reb3 to public/29683-reb4

[kliem]

Last 10 new commits:

6e4fb22	fix a variable name and add a doctest
45cffb0	typos
117a15e	another typo
5d2d329	improved documentation and check for elements to be of the correct polyhedron
6ee3093	typo
4cf2b76	ignore equations; make aliases
40cb506	small fixes
dae644e	fix segementation fault
fd50a98	check with a nice error for negative indices
644a803	better check for the far face containment

[kliem]

comment:81

Rebased on new version of #31834, which fixes trivial merge conflict because of whitespaces.

[kliem]

Changed commit from 644a803 to 99ddc2f

[kliem]

Changed branch from public/29683-reb4 to public/29683-reb5

[kliem]

comment:82

Only merged and rebased on #31834.

---

Last 10 new commits:

9cbd015	fix a variable name and add a doctest
4612fe5	typos
3b09b68	another typo
fe428aa	improved documentation and check for elements to be of the correct polyhedron
dd79e1c	typo
56c66a4	ignore equations; make aliases
80c80e5	small fixes
9afb276	fix segementation fault
ef5c95e	check with a nice error for negative indices
99ddc2f	better check for the far face containment

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

3e0229f	Merge tag '9.4.beta3' into t/31834/public/31834-reb2
8190917	Merge #31834

[sagetrac-git]

Changed commit from 99ddc2f to 8190917

[mkoeppe]

comment:84

easy merge of updated #31834

[mkoeppe]

comment:85

Back to positive review. LGTM too.

[mkoeppe]

Changed reviewer from Yuan Zhou to Yuan Zhou, Matthias Koeppe

[kliem]

comment:87

Thank you.

[vbraun]

Changed branch from public/29683-reb5 to 8190917