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:

Status badges

Description (last modified by mkoeppe)

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

Change History (14)

comment:1 Changed 4 years ago by mkoeppe

Description: modified (diff)
Summary: Polyhedron - lazy backend; minimal vs. non-minimal presentationsPolyhedron - lazy backend; minimal vs. non-minimal presentations; Polyhedron constructor with both Vrep, Hrep

comment:2 Changed 4 years ago by mkoeppe

Cc: jipilab added

comment:3 Changed 4 years ago by jipilab

Cc: slabbe added

comment:4 Changed 4 years ago by jipilab

Description: modified (diff)

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.

comment:5 Changed 21 months ago by mkoeppe

Cc: gh-kliem yzh added
Description: modified (diff)
Milestone: sage-wishlistsage-9.4
Summary: Polyhedron - lazy backend; minimal vs. non-minimal presentations; Polyhedron constructor with both Vrep, HrepPolyhedron constructors: minimal vs. non-minimal input representations; input both Vrep and Hrep

comment:6 Changed 21 months ago by mkoeppe

Branch: u/mkoeppe/polyhedron_constructors__minimal_vs__non_minimal_input_representations__input_both_vrep_and_hrep

comment:7 Changed 21 months ago by mkoeppe

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:

05fef94src/sage/geometry/polyhedron/constructor.py: Add more constructors

comment:8 Changed 19 months ago by mkoeppe

Milestone: sage-9.4sage-9.5

comment:9 Changed 14 months ago by mkoeppe

Milestone: sage-9.5sage-9.6

comment:10 Changed 11 months ago by mkoeppe

Milestone: sage-9.6sage-9.7

comment:11 Changed 10 months ago by gh-kliem

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 mkoeppe

Description: modified (diff)

comment:13 Changed 5 months ago by mkoeppe

Milestone: sage-9.7sage-9.8

comment:14 Changed 4 weeks ago by mkoeppe

Milestone: sage-9.8sage-9.9
Note: See TracTickets for help on using tickets.