Meta-ticket: Certified polyhedral computation

[mkoeppe]

Instead of just trusting that the output of a polyhedral algorithm (e.g., polyhedral representation conversion) is correct, we make them verifiable.

• The verification should be written in plain Python and should be as elementary as possible. For example - for LP, InteractiveLPProblem fits the bill - it implements textbook simplex method
• All transformations should be done by explicit maps

Algorithms:

• Certified polyhedral representation conversion: In the non-degenerate, bounded case, compute vertex/facet incidence; then verify for each vertex that the set of adjacent bases is correct. (When degeneracy is present, additional info may need to be computed in order to enable verification.)

• 31800 CombinatorialPolyhedron indexed by non-minimal H-representations

• 31799 From CombinatorialPolyhedron and H-representation to Polyhedron (with double description)

• Certified LP: #18735

• Certified polyhedral subdivisions and triangulations

Applications:

• 30202 Chamber of a parametric polyhedron

References

• TBD

CC: @yuan-zhou

Component: geometry

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

[mkoeppe]

Description changed:

--- 
+++ 
@@ -7,6 +7,8 @@
 - Certified polyhedral representation conversion: In the non-degenerate, bounded case, compute vertex/facet incidence; then verify for each vertex that the set of adjacent bases is correct. (When degeneracy is present, additional info may need to be computed in order to enable verification.)

 - Certified LP: #18735
+
+- Certified polyhedral subdivisions and triangulations

 Applications:

[mkoeppe]

Description changed:

--- 
+++ 
@@ -5,6 +5,8 @@

 Algorithms:
 - Certified polyhedral representation conversion: In the non-degenerate, bounded case, compute vertex/facet incidence; then verify for each vertex that the set of adjacent bases is correct. (When degeneracy is present, additional info may need to be computed in order to enable verification.)
+
+- #31799 From `CombinatorialPolyhedron` and `H-representation` to `Polyhedron` (with double description)

 - Certified LP: #18735

[mkoeppe]

Description changed:

--- 
+++ 
@@ -5,6 +5,8 @@

 Algorithms:
 - Certified polyhedral representation conversion: In the non-degenerate, bounded case, compute vertex/facet incidence; then verify for each vertex that the set of adjacent bases is correct. (When degeneracy is present, additional info may need to be computed in order to enable verification.)
+
+- #31800 `CombinatorialPolyhedron` indexed by non-minimal H-representations

 - #31799 From `CombinatorialPolyhedron` and `H-representation` to `Polyhedron` (with double description)