Polyhedron constructors: minimal vs. non-minimal input representations; input both Vrep and Hrep

[mkoeppe]

Follow-up from #17339 - Polyhedron class mistreats empty inputs.

As suggested in #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 in face.py
• "lazy" backend for Polyhedron

CC: @jplab @seblabbe @kliem @yuan-zhou

Component: geometry

Author: Matthias Koeppe, ...

Branch/Commit: u/mkoeppe/polyhedron_constructorsminimal_vs__non_minimal_input_representationsinput_both_vrep_and_hrep @ 05fef94

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

[mkoeppe]

Description changed:

--- 
+++ 
@@ -2,7 +2,9 @@
 Currently, `Polyhedron` does not support this; one either needs to work with lists of vertices or lists of inequalities; for an H-representation going through `MixedIntegerLinearProgram` is another option.

 A "lazy" backend for `Polyhedron` could be considered. 
+
 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).

+These questions would also need to be resolved for implementing a `Polyhedron` constructor that accepts both Vrep, Hrep (backend work for this appears on #22701, #26368). Related also: #17339 - Polyhedron class mistreats empty inputs

[jplab]

Description changed:

--- 
+++ 
@@ -7,4 +7,6 @@

 These questions would also need to be resolved for implementing a `Polyhedron` constructor that accepts both Vrep, Hrep (backend work for this appears on #22701, #26368). Related also: #17339 - Polyhedron class mistreats empty inputs

+FOLLOW-UP:

+- make this used in `as_polyhedron` method in `face.py`

[jplab]

comment:4

Here is just a note about constructing from both V- and H- representation:

The method as_polyhedron of PolyhedronFaces would benefit greatly from this, so perhaps as a follow-up or on this ticket.

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,12 +1,19 @@
-Sometimes it is convenient to set up a polytope without triggering the computation of the full (minimal) double description. 
-Currently, `Polyhedron` does not support this; one either needs to work with lists of vertices or lists of inequalities; for an H-representation going through `MixedIntegerLinearProgram` is another option.
+Follow-up from #17339 - Polyhedron class mistreats empty inputs.

-A "lazy" backend for `Polyhedron` could be considered. 
+As suggested in [#17339 comment:5](https://github.com/sagemath/sage/issues/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).

-These questions would also need to be resolved for implementing a `Polyhedron` constructor that accepts both Vrep, Hrep (backend work for this appears on #22701, #26368). Related also: #17339 - Polyhedron class mistreats empty inputs

-FOLLOW-UP:
+Follow-up / related:

 - make this used in `as_polyhedron` method in `face.py`
+- "lazy" backend for `Polyhedron`
+

[mkoeppe]

Branch: u/mkoeppe/polyhedron_constructorsminimal_vs__non_minimal_input_representationsinput_both_vrep_and_hrep

[mkoeppe]

Commit: 05fef94

[mkoeppe]

Author: Matthias Koeppe, ...

[mkoeppe]

comment:7

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

[kliem]

comment:11

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.

[mkoeppe]

Description changed:

--- 
+++ 
@@ -9,7 +9,7 @@
 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).
+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: