f_vector outputs an extra top-dimensional cell

[haraldschilly]

For a polytope whose dimension is less than its ambient dimension, the f_vector outputs an extra top-dimensional cell. For example, a triangle in 3-space:

INPUT

Polyhedron(vertices=[[0,0,0],[1,0,0],[0,1,0]]).f_vector()

OUTPUT

[1, 3, 3, 1, 1]

Expected Output

[1, 3, 3, 1]

Note, this was reported by the "report a problem" form.

CC: @novoselt

Component: geometry

Author: Volker Braun

Reviewer: Andrey Novoseltsev

Merged: sage-4.6.1.alpha1

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

[vbraun]

comment:1

The attached patch removes the old face_lattice() implementation and replaces it with Andrey's implementation of the same algorithm from sage/geometry/cone.py plus a few extensions to deal with general polyhedra. The function hasse_diagram_from_incidences is moved from cone.py to polyhedra.py. It also introduces a new class PolyhedronFace to abstract the faces. Now produces sane output on various degenerate polyhedra.

Patch might depend on #9798, #10148, #10024. Should be logically independent, but there will be some fuzz.

[vbraun]

Author: Volker Braun

[novoselt]

comment:2

Note also #8656.

A quick question: why was my function moved?-)

[vbraun]

comment:3

cone.py already imports from polyhedron.py and I didn't want to create a cyclic import :-)

[novoselt]

Reviewer: Andrey Novoseltsev

[novoselt]

comment:4

Shouldn't lines be added to all faces including the "empty one"? I am thinking here by analogy with equations that are "saturated" for all faces including the "full face". I agree that it is a bit weird, but I think this is correct from the point of view of dual representations.

I guess I then also want this "empty face" to have the dimension less by one then the dimension of the linear space generated by lines, by analogy to vertex - dimension 0, empty set - dimension -1. This is really weird, perhaps because in both cases "empty face" should have dimension -infinity?.. But it seems to me that "perfect duality" justifies a strange choice of dimension for a strange/empty face - if one works with such a face, he better know what he is doing. In which case, e.g. -1 is a great choice for the dimension of the empty face of a supporting polytope of a cone.

In the documentation the sentence "In the case of a full-dimensional polytope, the faces are pairs (vertices, inequalities) ..." needs some rewording - it is a bit misleading since faces are now represented by a special class (which is great, by the way!).

I didn't finish reading the patch yet, but hope to do so tomorrow.

[novoselt]

comment:5

I am getting fuzz applying this patch, probably because I have #9972 applied. If you are happy with the current version of that ticket, it would be convenient to have it pushed before this one ;-)

[novoselt]

comment:6

1. It seems that you wanted to cache the face lattice but forgot - the output of hasse_diagram_from_incidences is directly returned.
   1. Perhaps we should rename the method to Hasse...?
   2. PolyhedronFace constructor does not describe input.
   3. I think it would be nice to be able to treat polyhedron faces as polyhedrons themselves, in the way how it is done for cones. This is feasible only if creating new polyhedra is very fast, which is not the case now, but maybe it is something to think about in the future. As an easier to implement alternative, I would suggest adding a method polyhedron to PolyhedronFace that will produce a corresponding Polyhedron object. Note that this will clash with my desire to include lines to all faces including the bottom one. I am not sure what is the best option about it. Do you know what is the standard treatment in such situations?
   4. I think that new argument faces_at_infinity should be gone - it seems obscure to me and it is unnecessary. Currently you have replaced my line

head.extend(faces[frozenset([atom]), coatoms] 
    for atom, coatoms in enumerate(atom_to_coatoms))

with

for atom, coatoms in enumerate(atom_to_coatoms): 
    try: 
        head.append(faces[frozenset([atom]), coatoms]) 
    except KeyError, msg: 
        if not faces_at_infinity: 
 	    raise KeyError, msg 

but you can get the same result with

head.extend(faces[frozenset([atom]), coatoms] 
    for atom, coatoms in enumerate(atom_to_coatoms)
    if atoms_require_one_of is None or atom in atoms_require_one_of)

1. How about renaming atoms_require_one_of to required_atoms? I agree that your variant is more descriptive, but it sounds a bit weird as a parameter name.

[vbraun]

comment:7

I thought about adding lines to the "empty face", but I decided against it. There are certainly arguments for both. But in the end I decided against it because only lines would not be representable by a polyhedron. I don't have any reference, though.

When I refactor the Pohlyhedron class for ppl then I'll try to make PolyhedronFace derive from it. But right now its not feasible.

I'll include your other suggestions and will post a patch in a couple of days.

[vbraun]

comment:8

• capitalized Hasse_diagram_from_incidences.
  • added input documentation to PolyhedronFace constructor.
  • removed faces_at_infinity option and renamed atoms_require_one_of -> required_atoms .
  • fixed caching in Polyhedron.face_lattice().

[novoselt]

comment:9

One last pick - since cone module does not provide Hasse_diagram function anymore, it should not be mentioned at all in the beginning. I am fine with just removing the relevant paragraph completely, users should not use IntegralRayCollection anyway.

[novoselt]

comment:10

applying trac_9954_fix_face_lattice.patch
patching file sage/geometry/polyhedra.py
Hunk #2 succeeded at 129 with fuzz 2 (offset 0 lines).

(I have #10024 and #10148 applied, since they are already merged.)

[vbraun]

comment:11

I pulled the patches from #10024 and #10148 in front of this patch and fixed the module documentation.

[vbraun]

Updated patch

[novoselt]

comment:12

Attachment: trac_9954_fix_face_lattice.patch.gz

Great! Positive review!

[jdemeyer]

Merged: sage-4.6.1.alpha1