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