Dual algorithm for Face iterator of Unbounded Combinatorial Polyhedron

[xuluze]

Request

The dual algorithm for face iterator is not available for unbounded polyhedron. See the following small example:

C = Polyhedron(eqns=[[0, 0, -1, 1]], ieqs=[[0,1,0,0],[0,0,1,0],[0,0,0,1]]).combinatorial_polyhedron()
it = C.face_generator(algorithm='dual')
next(it)
it.ignore_supfaces()

ValueError: dual algorithm only available for bounded polyhedra

However, in the document https://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.html

It states "It also works on unbounded polyhedra, as those satisfy the diamond property, except for intervals including the empty face. A (slightly generalized) description of the algorithm can be found in [KS2019]."

Approach

The combinatorial polyhedron and the face iterator suffer from some design problems. While the equations have been removed from the combinatorial structure, the same has not been done with the linear subspace.

• We make the underlying structure always a polytope. This will simplify the algorithm a lot. The convention will be:
  • Equations and linear subspace are treated manually independently of the combinatorial structure. (This is already the case for equations).
  • The far facet will be added as the last facet.
  • Vertices and rays can be told apart by containment in the far facet.

Consequences

• For a polytope we just proceed as before.
• By marking the far facet as visited, we visit all faces of the polyhedron for the non-dual algorithm starting with the facets.
• We sort the generators to first visit the supfaces of the vertices. Then we just stop. This way we visit all faces with the dual algorithm.

Bonus

The definitions of simple and simplicial make sense for unbounded polyhedra as well and the simpliciations of the algorithm therefor work as well.

Suddenly we also have an algorithm to visit the bounded faces of a polyhedron:

• We ignore all supfaces of all rays. Then we visit all bounded faces with the dual algorithm.

CC: @mkoeppe

Component: geometry

Author: Jonathan Kliem

Branch/Commit: public/34773/dual_face_iterator_for_unbounded_polyhedra @ be060ce

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

[mkoeppe]

comment:1

@kliem Would this be easy to implement?

[xuluze]

Description changed:

--- 
+++ 
@@ -1 +1,16 @@
+The dual algorithm for face iterator is not available for unbounded polyhedron. See the following small example:

+```python
+C = Polyhedron(eqns=[[0, 0, -1, 1]], ieqs=[[0,1,0,0],[0,0,1,0],[0,0,0,1]]).combinatorial_polyhedron()
+it = C.face_generator(algorithm='dual')
+next(it)
+it.ignore_supfaces()
+```
+
+`ValueError: dual algorithm only available for bounded polyhedra`
+
+However, in the document https://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.html#sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.FaceIterator
+
+It states "It also works on unbounded polyhedra, as those satisfy the diamond property, except for intervals including the empty face. A (slightly generalized) description of the algorithm can be found in [KS2019]." 
+
+I am wondering how hard it will be to adapt the current code to the unbounded polyhedra. Thank you!

[xuluze]

Description changed:

--- 
+++ 
@@ -9,7 +9,7 @@

 `ValueError: dual algorithm only available for bounded polyhedra`

-However, in the document https://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.html#sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.FaceIterator
+However, in the document https://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.html

 It states "It also works on unbounded polyhedra, as those satisfy the diamond property, except for intervals including the empty face. A (slightly generalized) description of the algorithm can be found in [KS2019]." 

[kliem]

comment:4

I don't think it is very hard. How urgent is it? Or is it just to have it.

It is just that I messed this up in the beginning, as I didn't know any better.

The real work might be to clean up along the way. Some stuff is just way too complicated and might be a huge pain to maintain (and is already very difficult to compensate for everyone not directly involved, maybe even everyone except me).

[xuluze]

comment:5

In our case, we can try to get around it by adding a hyperplane to make the cone bounded, and be careful to identify the original faces when handling with the face iterator. But it would be nice to have the dual algorithm apply to our unbounded case directly to make the code cleaner.

[kliem]

comment:6

Something like:

sage: P = Polyhedron(rays=[[1,0,0], [0,1,0], [0,1,1]])
sage: C = P.combinatorial_polyhedron()
sage: facets = C.facets()
sage: far_face = P.rays()
sage: new_facets = facets + (far_face,)
sage: C1 = CombinatorialPolyhedron(new_facets)
sage: it = C1.face_iter(algorithm='dual')
sage: faces = [i for i in it if any(v.is_vertex() for v in i.ambient_Vrepresentation())]

should work as a workaround.

[xuluze]

comment:7

Thank you very much! Yes, it works.

[kliem]

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
+**Request**
+
 The dual algorithm for face iterator is not available for unbounded polyhedron. See the following small example:

 ```python
@@ -11,6 +13,26 @@

 However, in the document https://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.html

-It states "It also works on unbounded polyhedra, as those satisfy the diamond property, except for intervals including the empty face. A (slightly generalized) description of the algorithm can be found in [KS2019]." 
+It states "It also works on unbounded polyhedra, as those satisfy the diamond property, except for intervals including the empty face. A (slightly generalized) description of the algorithm can be found in [KS2019]."

-I am wondering how hard it will be to adapt the current code to the unbounded polyhedra. Thank you!
+**Approach**
+
+The combinatorial polyhedron and the face iterator suffer from some design problems. While the equations have been removed from the combinatorial structure, the same has not been done with the linear subspace.
+
+- We make the underlying structure always a polytope. This will simplify the algorithm a lot. The convention will be:
+  - Equations and linear subspace are treated manually independently of the combinatorial structure. (This is already the case for equations).
+  - The far facet will be added as the last facet.
+  - Vertices and rays can be told apart by containment in the far facet.
+
+**Consequences**
+
+- For a polytope we just proceed as before.
+- By marking the far facet as visited, we visit all faces of the polyhedron for the non-dual algorithm starting with the facets.
+- We sort the generators to first visit the supfaces of the vertices. Then we just stop. This way we visit all faces with the dual algorithm.
+
+**Bonus**
+
+Suddenly we also have an algorithm to visit the bounded faces of a polyhedron:
+- We first treat all facets and treat the far facet last (or rather don't treat it at all).
+- We ignore all supfaces of all rays. Then we visit all bounded faces with the dual algorithm.
+

[kliem]

Author: Jonathan Kliem

[kliem]

Description changed:

--- 
+++ 
@@ -32,6 +32,8 @@

 **Bonus**

+The definitions of simple and simplicial make sense for unbounded polyhedra as well and the simpliciations of the algorithm therefor work as well.
+
 Suddenly we also have an algorithm to visit the bounded faces of a polyhedron:
 - We first treat all facets and treat the far facet last (or rather don't treat it at all).
 - We ignore all supfaces of all rays. Then we visit all bounded faces with the dual algorithm.

[mkoeppe]

Suddenly we also have an algorithm to visit the bounded faces of a polyhedron:

Great - that will also be useful for computing regular subdivisions

[kliem]

comment:11

Unfortunatly, I had to remove some nonsense. the bounded faces starting from the facets are a bit annoying and I don't know a shortcut to visiting all faces and filtering.

Starting from the vertices there is a shortcut I think. At least the implementation is easy. If there are few vertices and many many rays, the assymtotics are a bit annoying: # bounded faces # generators # vertices * # facets.

If the generators are in general position that is much nicer: # bounded faces # vertices max(# vertices, # facets).

(Subject to stupid mistakes I made because I'm tired.)

Edit: The generators need to be in general position.

[kliem]

Description changed:

--- 
+++ 
@@ -35,6 +35,5 @@
 The definitions of simple and simplicial make sense for unbounded polyhedra as well and the simpliciations of the algorithm therefor work as well.

 Suddenly we also have an algorithm to visit the bounded faces of a polyhedron:
-- We first treat all facets and treat the far facet last (or rather don't treat it at all).
 - We ignore all supfaces of all rays. Then we visit all bounded faces with the dual algorithm.

[kliem]

Commit: 96538d1

[kliem]

New commits:

55afcda	fix(34773): Update email adresses
96538d1	feat(34773): Move list of pairs to dedicated class

[kliem]

Branch: public/34773/dual_face_iterator_for_unbounded_polyhedra

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

95a9fe0	refactor(34773): Move list of pairs to dedicated class
c1f0186	refactor(34773): Simplify methods of combinatorial polyhedron

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 96538d1 to c1f0186

[kliem]

comment:14

There is actually one thing one needs to pay attention to:

A far face is not always a far facet:

E.g. Polyhedron(vertices=[[1, 0], [0, 1]], rays=[[1, 1]]) is unbounded, but does not have a far facet.

But Polyhedron(vertices=[[1, 0], [0, 1]], rays=[[1, 0], [0, 1]]) has a far facet.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c1f0186 to 722ceb9

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ba07715	fix(34773): Update email adresses
2c304a8	refactor(34773): Move list of pairs to dedicated class
8b8e94a	refactor(34773): Simplify methods of combinatorial polyhedron
722ceb9	refactor(34773): Refactor a bit of the CombinatorialPolyhedron initialization

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

be060ce

fixup! refactor(34773): Refactor a bit of the CombinatorialPolyhedron initialization

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 722ceb9 to be060ce

[kliem]

I think I need to do some refactoring, before I can make any changes. That code is awful :-)

I have created as a first step: https://github.com/sagemath/sage/pull/35073

Is it okay to link multiple pull requests to an issue or do we need one issue per pull request?

[mkoeppe]

You can mention the issue in many PRs, but only one of them (the last one) should say "Closes ...".

[kliem]

Btw, it seems I'm lacking the right to add tags like "needs review".

[mkoeppe]

I've sent an invite to the Triage team to you