Opened 3 years ago

Last modified 7 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.6
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).

Follow-up / related:

  • make this used in as_polyhedron method in face.py
  • "lazy" backend for Polyhedron

Change History (9)

comment:1 Changed 3 years ago by mkoeppe

  • Description modified (diff)
  • Summary changed from Polyhedron - lazy backend; minimal vs. non-minimal presentations to Polyhedron - lazy backend; minimal vs. non-minimal presentations; Polyhedron constructor with both Vrep, Hrep

comment:2 Changed 3 years ago by mkoeppe

  • Cc jipilab added

comment:3 Changed 3 years ago by jipilab

  • Cc slabbe added

comment:4 Changed 3 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 8 months ago by mkoeppe

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

comment:6 Changed 8 months ago by mkoeppe

  • Branch set to u/mkoeppe/polyhedron_constructors__minimal_vs__non_minimal_input_representations__input_both_vrep_and_hrep

comment:7 Changed 8 months ago by mkoeppe

  • Authors set to Matthias Koeppe, ...
  • Commit set to 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 6 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:9 Changed 7 weeks ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6
Note: See TracTickets for help on using tickets.