Opened 4 years ago
Last modified 4 weeks ago
#26366 new enhancement
Polyhedron constructors: minimal vs. non-minimal input representations; input both Vrep and Hrep
Reported by: | mkoeppe | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.9 |
Component: | geometry | Keywords: | |
Cc: | jipilab, slabbe, gh-kliem, 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 )
Follow-up 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 V-represenation, such as vertex_generator
; but not in those for the H-representation (inequality_generator
). (Note the minimize
argument is unused in the whole Polyhedron
code.) Compare with polymake, which has a clear distinction between minimal and non-minimal presentations (VERTICES vs. POINTS). This ia addressed in #34327.
Follow-up / 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. non-minimal presentations → Polyhedron - lazy backend; minimal vs. non-minimal 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: | gh-kliem yzh added |
---|---|
Description: | modified (diff) |
Milestone: | sage-wishlist → sage-9.4 |
Summary: | Polyhedron - lazy backend; minimal vs. non-minimal presentations; Polyhedron constructor with both Vrep, Hrep → Polyhedron constructors: minimal vs. non-minimal 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: | sage-9.4 → sage-9.5 |
---|
comment:9 Changed 14 months ago by
Milestone: | sage-9.5 → sage-9.6 |
---|
comment:10 Changed 11 months ago by
Milestone: | sage-9.6 → sage-9.7 |
---|
comment:11 Changed 10 months ago by
What is the status here?
I think the minimal/non-minimal 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: | sage-9.7 → sage-9.8 |
---|
comment:14 Changed 4 weeks ago by
Milestone: | sage-9.8 → sage-9.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 follow-up or on this ticket.