HPolytope

Bases: Polytope

A lattice polytope constructed from hyperplane inequalities.

An HPolytope is specified by an H-representation, i.e. a list of linear inequalities. The polytope cut out by the inequalities need not be a lattice polytope (its vertices may be rational), so it is converted into one in one of two ways:

1. By taking its integer hull, i.e. the convex hull of the lattice points it contains (the default).
2. By rescaling it by the smallest positive factor that makes all of its vertices integral (dilate=True). The result is normally equivalent to the original polytope.

Both notions agree with the original polytope if and only if it is already a lattice polytope. The resulting lattice polytope is then used to construct the parent Polytope object, so all of its methods are available.

If every constant term \(c_{i,d}\) equals 1, the inequalities describe the polar dual of the convex hull of the normal vectors, and the vertices are computed from the facets of that convex hull. Otherwise, they are computed with PPL. If the inequalities have no solution, an empty (-1-dimensional) polytope is constructed.

Parameters:

• ineqs (ArrayLike, default: None ) –

  The defining inequalities, as a matrix \(c\) where each row \(c_i\) encodes the inequality \(c_{i,0}x_0 + \dots + c_{i,d-1}x_{d-1} + c_{i,d} \geq 0\), with \(d\) the ambient dimension. They must define a bounded region.

• dilate (bool, default: False ) –

  Whether to rescale the polytope so that it becomes a lattice polytope, instead of taking its integer hull.

• backend (str | None, default: None ) –

  The backend used to construct the convex hull. The options are "ppl", "qhull", and "palp". If not specified, PPL is used when all constant terms equal 1; otherwise the default of Polytope is used (PPL for dimensions up to four and PALP otherwise).

• verbosity (int, default: 0 ) –

  The verbosity level.

Raises:

• ValueError –

  If ineqs is not given or is not a 2D matrix, if the region they define is unbounded, or if taking the integer hull and the polytope contains no lattice points.

Examples:

We construct the triangle with vertices \((0,0)\), \((1/2,0)\) and \((0,3/2)\), which is not a lattice polytope. By default, its integer hull is computed, while with dilate=True it is rescaled into a lattice polytope.

>>> from cytools import HPolytope
>>> ineqs = [[1,0,0],[0,1,0],[-6,-2,3]]
>>> HPolytope(ineqs).vertices()
array([[0, 0],
       [0, 1]])
>>> HPolytope(ineqs, dilate=True).vertices()
array([[0, 0],
       [0, 3],
       [1, 0]])

When all constant terms are 1, the polytope is the polar dual of the convex hull of the normal vectors.

>>> p = HPolytope([[1,0,1],[0,1,1],[-1,-1,1]])
>>> p.vertices()
array([[-1, -1],
       [-1,  2],
       [ 2, -1]])
>>> p.is_reflexive()
True

Source on GitHub