Opened 19 months ago
Closed 9 months ago
#26922 closed defect (fixed)
Wrong fvector for unbounded polyhedra
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.0 
Component:  geometry  Keywords:  
Cc:  jipilab, moritz  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  1c5378c (Commits)  Commit:  1c5378cd38b1f65717a2556ae7dc9ca7f756a150 
Dependencies:  #28625  Stopgaps: 
Description (last modified by )
#28625 fixed the f_vector
in the case of unpointed polyhedra/polyhedra with lines.
We add doctests showing that #28625 fixed a bug in f_vector
.
Before:
sage: Polyhedron(ieqs=[[1,1,0],[1,1,0]]).f_vector() (1, 2, 1)
But this polyhedron does not have zerodimensional faces, and #28625 has correctly changed that:
sage: Polyhedron(ieqs=[[1,1,0],[1,1,0]]).f_vector() (1, 0, 2, 1)
Also we add documentation, specifically warning users that the methods
vertices
,vertices_list
,vertices_generator
vertices_matrix
,n_vertices
,
treat vertices of the Vrepresentation
and not vertices of the polyhedron in the unpointed case.
Change History (16)
comment:1 Changed 18 months ago by
comment:2 Changed 18 months ago by
 Milestone changed from sage8.6 to sage8.7
Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sagepending or sagewishlist.
comment:3 Changed 16 months ago by
 Milestone changed from sage8.7 to sage8.8
comment:4 Changed 13 months ago by
 Milestone sage8.8 deleted
As the Sage8.8 release milestone is pending, we should delete the sage8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage8.9).
comment:5 followup: ↓ 6 Changed 12 months ago by
In principle, the problem is that the face lattice has four elements, but the elements on the second level are not 0dimensional, but 1dimensional.
So, depending on the definition of the fvector:
 Counting the number of elements at each level of the face lattice
 Vector counting the number of faces by dimension
It should return different things.
One thing that should be done, is to make this explicit in the documentation of f_vector
once this ticket is fixed and give an example of the difference with unbounded polyhedra.
comment:6 in reply to: ↑ 5 Changed 12 months ago by
#27063 will change the calculation of the fvector (hopefully soon) to make use of CombinatorialPolyhedron
.
This will count the number of faces per dimension, as the docstring of f_vector
states (there is a +2 or 2 two missing, as the first entry gives the 1dimensional faces count.
We could make this ticket depend on #27063 and then just append the docstring accordingly.
One could also fix it for now (just append a few zeros according to n_lines
).
Replying to jipilab:
In principle, the problem is that the face lattice has four elements, but the elements on the second level are not 0dimensional, but 1dimensional.
So, depending on the definition of the fvector:
 Counting the number of elements at each level of the face lattice
I think fvectors of fixed dimension polyhedra should be have sums/addition. Also if one considers how adding or deleting inequalities can alter the fvector this is strange. Anyway, it's most important to be precise, which one we use. Adding a zero or deleting it, if one really depends one version is trivial.
 Vector counting the number of faces by dimension
It should return different things.
One thing that should be done, is to make this explicit in the documentation of
f_vector
once this ticket is fixed and give an example of the difference with unbounded polyhedra.
comment:7 Changed 9 months ago by
ping!
comment:8 Changed 9 months ago by
 Branch set to public/26922
 Commit set to 3c9085ec178d0ad052612d9db53fe588940fe48a
 Dependencies set to #28625
 Milestone set to sage9.0
 Status changed from new to needs_review
#28625 fixes this.
I added some tests, improved the documentation of f_vector
and fixed a tiny typo.
New commits:
b89610e  added combinatorial polyhedron as an attribute for polyhedra

326602c  f_vector of CombinatorialPolyhedron is a vector

dfbe2ad  Merge branch 'public/28607' of git://trac.sagemath.org/sage into public/28621

ed5518b  used CombinatorialPolyhedron to compute f_vector

9bdd005  give an error message for polytopes in some cases; removed incorrect example

acd671d  now we get a precice error message for inexact truncated dodecahedron

bf85a62  subsequent calls for f_vector fail if first attempt fails

3c9085e  give doctests that f_vector for unbounded polyhedra works now

comment:9 Changed 9 months ago by
 Status changed from needs_review to needs_work
It would be nice if the note that you gave be in a NOTE environment followed by an appropriate example illustrating what is meant.
comment:10 Changed 9 months ago by
 Commit changed from 3c9085ec178d0ad052612d9db53fe588940fe48a to cbcc4c42cb427c2967097098d00a771a6d47eb44
Branch pushed to git repo; I updated commit sha1. New commits:
cbcc4c4  Comment to f_vector in NOTE environment; warnings of ambigious meaning of vertex

comment:11 Changed 9 months ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
comment:12 Changed 9 months ago by
 Cc moritz added; mortiz removed
 Reviewers set to JeanPhilippe Labbé
 Status changed from needs_review to needs_work
May I suggest the following:
 In case of a polyhedron with lines (unpointed polyhedron),  return the number of vertices of the ``Vrepresentation``.  Wheras the polyhedron has no vertices, this number corresponds  to the number of `k`faces, where `k` is the number of lines. + If the polyhedron has lines, returns the number of vertices in + the ``Vrepresentation``. As the represented polyhedron has + no 0dimensional faces (i.e. vertices), this number corresponds + to the number of `k`faces, where `k` is the number of lines.
Somehow, even though I corrected the above warning. I do not like what it says at all for the following reason:
sage: P = Polyhedron(rays=[[1,0,0]],lines=[[0,1,0]]) sage: P.vertices() (A vertex at (0, 0, 0),) sage: Q = Polyhedron(lines=[[0,1,0],[0,0,1]]) sage: Q.vertices() (A vertex at (0, 0, 0),) sage: R = Polyhedron(rays=[[1,0,0],[0,1,0]],vertices=[[0,1,0],[1,0,0]],lines=[[0,0,1]]) sage: R.vertices() (A vertex at (0, 1, 0), A vertex at (1, 0, 0))
In Sage, the computational convention (or compromise) is that polyhedra without vertices in their Vrepresentation still receive a canonically computed vertex in order to do computations.
With this in mind, the second sentence is wrong. Just look at the above polyhedron R
. It has lines, and two vertices.
> This warning is more confusing than anything. Please rephrase taking the above three examples in mind and the convention in Sage.
comment:13 Changed 9 months ago by
 Commit changed from cbcc4c42cb427c2967097098d00a771a6d47eb44 to 1c5378cd38b1f65717a2556ae7dc9ca7f756a150
Branch pushed to git repo; I updated commit sha1. New commits:
1c5378c  clearified warnings

comment:14 Changed 9 months ago by
 Status changed from needs_work to needs_review
comment:15 Changed 9 months ago by
 Status changed from needs_review to positive_review
Looks good to me now
comment:16 Changed 9 months ago by
 Branch changed from public/26922 to 1c5378cd38b1f65717a2556ae7dc9ca7f756a150
 Resolution set to fixed
 Status changed from positive_review to closed
This will be probably solved at some point by #26887 The calculation is correct there.
Also it can be corrected quickly now by calculating the dimension of the first level in the face lattice.