Opened 4 years ago
Last modified 4 weeks ago
#26366 new enhancement
Polyhedron constructors: minimal vs. nonminimal input representations; input both Vrep and Hrep
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage9.9 
Component:  geometry  Keywords:  
Cc:  jipilab, slabbe, ghkliem, yzh  Merged in:  
Authors:  Matthias Koeppe, ...  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/mkoeppe/polyhedron_constructors__minimal_vs__non_minimal_input_representations__input_both_vrep_and_hrep (Commits, GitHub, GitLab)  Commit:  05fef94a5c8e3317daae7ffc996ff4f87e0443ac 
Dependencies:  Stopgaps: 
Description (last modified by )
Followup from #17339  Polyhedron class mistreats empty inputs.
As suggested in https://trac.sagemath.org/ticket/17339#comment:5, we complement the Polyhedron
constructor with several new constructors with simpler semantics.
Polyhedron.from_Vrep
Polyhedron.from_Hrep
Polyhedron.empty
We also add a constructor Polyhedron.from_Vrep_and_Hrep
that accepts both Vrep and Hrep (backend work for this appears on #22701, #26368).
But there are open questions regarding the possible design. All Polyhedron
methods currently guarantee minimal representations. This is reflected also in the names of methods for accessing the Vrepresenation, such as vertex_generator
; but not in those for the Hrepresentation (inequality_generator
). (Note the minimize
argument is unused in the whole Polyhedron
code.) Compare with polymake, which has a clear distinction between minimal and nonminimal presentations (VERTICES vs. POINTS). This ia addressed in #34327.
Followup / related:
 make this used in
as_polyhedron
method inface.py
 "lazy" backend for
Polyhedron
Change History (14)
comment:1 Changed 4 years ago by
Description:  modified (diff) 

Summary:  Polyhedron  lazy backend; minimal vs. nonminimal presentations → Polyhedron  lazy backend; minimal vs. nonminimal presentations; Polyhedron constructor with both Vrep, Hrep 
comment:2 Changed 4 years ago by
Cc:  jipilab added 

comment:3 Changed 4 years ago by
Cc:  slabbe added 

comment:4 Changed 4 years ago by
Description:  modified (diff) 

comment:5 Changed 21 months ago by
Cc:  ghkliem yzh added 

Description:  modified (diff) 
Milestone:  sagewishlist → sage9.4 
Summary:  Polyhedron  lazy backend; minimal vs. nonminimal presentations; Polyhedron constructor with both Vrep, Hrep → Polyhedron constructors: minimal vs. nonminimal input representations; input both Vrep and Hrep 
comment:6 Changed 21 months ago by
Branch:  → u/mkoeppe/polyhedron_constructors__minimal_vs__non_minimal_input_representations__input_both_vrep_and_hrep 

comment:7 Changed 21 months ago by
Authors:  → Matthias Koeppe, ... 

Commit:  → 05fef94a5c8e3317daae7ffc996ff4f87e0443ac 
This is an early draft, with the purpose of supporting #31799. Comments and improvements to the design are very welcome.
One thing needed for #31799 is finding the parent early  then, for parents that implement init from both representations, one could efficiently compute the double description before calling the element constructor.
New commits:
05fef94  src/sage/geometry/polyhedron/constructor.py: Add more constructors

comment:8 Changed 19 months ago by
Milestone:  sage9.4 → sage9.5 

comment:9 Changed 14 months ago by
Milestone:  sage9.5 → sage9.6 

comment:10 Changed 11 months ago by
Milestone:  sage9.6 → sage9.7 

comment:11 Changed 10 months ago by
What is the status here?
I think the minimal/nonminimal issue should really be fixed. In a way, it is only relevant for Polyhedron_mutual
. If the backend doesn't allow modification, then what is the point in being lazy?
I really don't know what name choices what make sense and involve little deprecation.
Do we need anything but minimal representation? For the input sure, but once you are asking for Vrepresentation
or Hrepresentation
or inequalities
, you usually want something minimal. But then again, if I construct P
and Q
only to compute their intersection, I don't care about the minimal inequalities in many cases.
comment:12 Changed 6 months ago by
Description:  modified (diff) 

comment:13 Changed 5 months ago by
Milestone:  sage9.7 → sage9.8 

comment:14 Changed 4 weeks ago by
Milestone:  sage9.8 → sage9.9 

Here is just a note about constructing from both V and H representation:
The method
as_polyhedron
ofPolyhedronFaces
would benefit greatly from this, so perhaps as a followup or on this ticket.