Opened 11 years ago

Closed 10 years ago

#8656 closed defect (duplicate)

face_lattice does not seem to work for unbounded polyhedra

Reported by: novoselt Owned by: mhampton
Priority: major Milestone: sage-4.6.1
Component: geometry Keywords:
Cc: vbraun Merged in:
Authors: Volker Braun Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges


Recent ticket #8650 (required for the output below) fixed a bug in face_lattice computation for polytopes. However, I think that both of the following examples for unbounded polyhedra are incorrect.

sage: for lset in Polyhedron(rays=[(1,0)]).face_lattice().level_sets(): lset
[(None, (0, 1))]
[((0,), (0,)), ((1,), (0, 1))]
[((0, 1), (0,))]
[((0, 1), None)]

This ray has three faces: empty, vertex, and the whole ray (including the vertex at which it originates). Five are shown, including a face containing the ray, but not the vertex from which it originates.

sage: for lset in Polyhedron(rays=[(1,0), (0,1)]).face_lattice().level_sets(): lset
[(None, (0, 1))]
[((1,), (0,)), ((0,), (1,)), ((2,), (0, 1))]
[((1, 2), (0,)), ((0, 2), (1,))]
[((0, 1, 2), None)]

For the quadrant we have five faces: empty, vertex, two rays, and the whole quadrant. The above output has seven.

The easiest fix is probably to raise an exception if the polyhedron is unbounded and state in the documentation that face_lattice works only for polytopes, but of course it would be nice to be able to compute correct faces in all cases.

Change History (9)

comment:1 Changed 11 years ago by vbraun

The non-compactness is not the issue, the 1-d interval in a 2-d ambient space fails as well:

sage: for lset in Polyhedron(vertices=[(1,0),(0,1)]).face_lattice().level_sets(): print lset
[(None, (0, 1, 2))]
[((1,), (0, 2)), ((0,), (0, 1))]
[((0, 1), (0,))]
[((0, 1), None)]

On the other hand, I would argue that the novoselt's Quadrant example is correct: The rays stand for points at infinite distance and are properly counted as points. A triangle would have 8 faces. The edge at infinity is not counted as a face of the quadrant (=double infinite triangle), hence the quadrant does have 7 faces.

The fundamental flaw of the face_lattice() function is that 1) its description does not explain in detail what is computed 2) The result should be returned by means of the H/Vrepresentation objects, and not by their indices.

comment:2 Changed 11 years ago by vbraun

  • Cc vbraun added

comment:3 Changed 11 years ago by novoselt

Well, what exactly is a face of a convex polyhedron in an affine space? I take as the definition "an intersection of a supporting hyperplane with the polyhedron." In this case rays cannot appear "by themselves," without the vertex from which they are going.

I think that you actually agree with me ;-) Why did you throw away the "edge at infinity?" I think, because it is "completely at infinity." But the same is true for a standalone ray representing "a vertex at infinity" - this face has no points in the affine space. On the other hand, "a half-infinite" edge defined by a vertex and a ray lives in the affine space except for one endpoint. So I would argue that we should throw away all faces generated by infinite point only. Or at least do this by default and have an option to include them, but then I think that ALL infinite faces should be included.

Actually, just a couple of days ago I have implemented the algorithm used for face_lattice following the reference in the documentation (and my implementation seems to be faster, but it is not yet ready for inclusion).

This algorithm computes the Hasse diagram of an atomic and coatomic lattice starting from incidences. In the case of a bounded full-dimensional polyhedron vertices are atoms and facets are coatoms. If the polytope includes rays and lines in addition to vertices and equations in addition to inequalities, one should be more careful.


comment:4 Changed 11 years ago by vbraun

I tend to think of non-compact polyhedra in R^n as compact polyhedra in RP^n. This is also what TOPCOM and, I think, cdd do (though its never spelled out in the cdd manual). The faces of the non-compact polyhedron consist of all faces of the projective polyhedron that can be spanned by affine points and rays.

I think the rationale is that you tend to do this if you naively apply an algorithm for compact polyhedra in the non-compact case.

Though I agree that, from a user perspective, your definition of faces (always including at least one vertex) would be nicer. However, I think you can not derive it from the incidence matrix alone but you will have to distinguish cases for the different H/V-representation objects. It would be great if you could polish your implementation for inclusion. Let me know if I can help with anything. I do need a working face lattice for non-compact polyhedra for the toric varieties package I'm currently working on...

comment:5 Changed 11 years ago by novoselt

Actually, it is a part of my modules for cones/fans/toric varieties/fano toric varieties/Calabi-Yau hypersurfaces and complete intersections inside them. We should probably coordinate our efforts. At what stage is your work?

comment:6 Changed 11 years ago by vbraun

I've implemented all the fan/lattice basics, cohomology and Chern clases, Chow ring, divisors, Mori cone.

The current status is at, documentation is at

comment:7 Changed 10 years ago by vbraun

  • Milestone changed from sage-4.6 to sage-4.6.1
  • Status changed from new to needs_review

Fixed by the patch in #9954:

sage: for lset in Polyhedron(rays=[(1,0)]).face_lattice().level_sets(): lset
sage: sage: for lset in Polyhedron(rays=[(1,0), (0,1)]).face_lattice().level_sets(): lset
[<1,2>, <0,2>]

This ticket can be closed once #9954 is merged.

comment:8 Changed 10 years ago by novoselt

  • Authors set to Volker Braun
  • Reviewers set to Andrey Novoseltsev
  • Status changed from needs_review to positive_review

Indeed, #9954 fixes the problem, so this ticket should be closed.

comment:9 Changed 10 years ago by jdemeyer

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.