Module polytope 

Exact convex polyhedra in ℚⁿ from half-spaces: vertices, volume, containment, cutting. Exact convex polyhedra in ℚⁿ given by half-spaces.

A Polytope is an intersection of half-spaces aᵢ·x + bᵢ ≥ 0 with rational data. Everything here is exact: vertices come from solving n × n systems with the fraction-free kernel behind QMatrix, emptiness and boundedness from the exact LP, volumes (any dimension) from an exact facet decomposition around the vertex centroid. The type is meant for the geometric bookkeeping around certificate searches — which cells a decision tree produces, where to cut them, whether two descriptions coincide — not for large polyhedra: vertices is O(C(m, n)) linear solves.

Examples

use symplex::polytope::Polytope;
use symplex::linprog::{q, qi};

// The triangle 0 ≤ x, 0 ≤ y, x + y ≤ 1, described with a redundant face x ≤ 2.
let tri = Polytope::from_rows(&[
    (vec![qi(1), qi(0)], qi(0)),     //  x ≥ 0
    (vec![qi(0), qi(1)], qi(0)),     //  y ≥ 0
    (vec![qi(-1), qi(-1)], qi(1)),   //  1 − x − y ≥ 0
    (vec![qi(-1), qi(0)], qi(2)),    //  2 − x ≥ 0   (redundant)
]).unwrap();
let v = tri.vertices().unwrap();
assert_eq!(v.len(), 3);
assert_eq!(tri.volume().unwrap(), q(1, 2));
assert!(tri.contains(&[q(1, 4), q(1, 4)]));
assert_eq!(tri.irredundant().unwrap().num_halfspaces(), 3);
let halves = tri.split(&[qi(-1), qi(0)], q(1, 2));   // cut at x = 1/2
assert_eq!(halves.nonnegative.volume().unwrap() + halves.nonpositive.volume().unwrap(), q(1, 2));

Structs

Clip

The result of Polytope::clip: the vertex sets of the two closed pieces of a polytope cut by a hyperplane, in no particular order.

HalfSpace

One half-space coeffs · x + constant ≥ 0.

ParametricPolytope

A family of polytopes {x : hₖ(j, x) ≥ 0} whose half-spaces are affine in x with coefficients polynomial in one parameter j.

Polytope

A convex polyhedron {x ∈ ℚⁿ : aᵢ·x + bᵢ ≥ 0 ∀i}.

Split

The two closed pieces of a polytope cut by a hyperplane coeffs·x + constant = 0 (see Polytope::split).

Type Aliases

BoundingBox

Per-coordinate [min, max] of a polytope; an absent side is unbounded.

TightVertex

A vertex with its tight set: the point and the ascending indices (into Polytope::halfspaces) of the non-trivial half-spaces whose hyperplane passes through it. See Polytope::vertices_with_tight.